Counting Sort (계수정렬)

| O(n) 정렬

비교 정렬의 하한은 O(nlogn)이지만 입력된 자료의 원소가 제한적인 성질을 만족하는 경우 O(n) 정렬이 가능하다. 대표적인 O(n) 정렬의 알고리즘으로는 Counting Sort와 Radix Sort가 있다.

---

| Counting Sort

일반적으로 정수 또는 문자를 정렬하는 경우 많이 사용되는 방법으로, 원소의 범위가 제한적일 때 원소의 개수를 세어 정렬하는 방법이다. 개수를 셀 배열과 정렬된 결과가 저장될 배열이 추가로 필요하다. 다양한 구현 방법이 있지만, Radix Sort와 연관된 버전으로 알아보자.

기본 구현 방법은 아래와 같다.
1. 각 원소의 개수를 저장할 count 배열을 준비한다.
2. 정렬한 배열에 대하여 각 원소의 개수를 세어 count 배열에 저장한다.

int arr_len = 20, count_arr_len = 6; // 배열 arr에 등장하는 원소의 범위가 (0~5) 라고 가정
int i; 

for(i=0; i<count_arr_len; i++) count[i] = 0;	// 배열 초기화
for(i=0; i<arr_len; i++) count[arr[i]]++; 		// 카운팅

3. count의 누적합을 구한다.
4. count 배열과 원래 배열 arr을 이용하여 정렬된 결과 sorted_arr 배열을 구한다.

for(i = 1; i<count_arr_len; i++) count[i] += count[i-1]; // 누적합
for(i = arr_len - 1; i>=0; i--) {
	sorted_arr[--count[arr[i]] = arr[i];
}

정리하자면 아래와 같이 구현할 수 있다.

// arr 원소의 범위를 (0~5) 라고 가정
int arr_len = 20, count_arr_len = 6;
int i; 

for(i=0; i<count_arr_len; i++) count[i] = 0;	// 배열 초기화
for(i=0; i<arr_len; i++) count[arr[i]]++; 		// 카운팅
for(i = 1; i<count_arr_len; i++) count[i] += count[i-1]; // 누적합
for(i = arr_len - 1; i>=0; i--) {
	sorted_arr[--count[arr[i]] = arr[i];
}

 

이와 연계한 Radix Sort는 아래 포스트를 참고한다. 

https://googleyness.tistory.com/entry/Radix-Sort-%EA%B8%B0%EC%88%98-%EC%A0%95%EB%A0%AC

Radix Sort (기수 정렬)