Sort Algorithm

08. 계수 정렬 (Counting Sort)

앞서 여러 정렬 방법들에 대해 공부했다. 빠른 정렬을 말하라면, 퀵 / 병합 / 힙 정렬을 말할 수 있다.

하지만, 이들 보다 더 빠르게 정렬을 해야 한다면 어떻게 해야할까?

/* 다음 5 이하 정수 데이터들을 오름차순으로 정렬하라 */

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

이 예시에서는, 데이터 개수는 30개이다. 다만, 데이터의 조건이 1~5 사이에 속한다는 범위 조건이 존재한다. 이렇게 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘이다.

계수 정렬은 단순하게 ‘크기를 기준으로 갯수를 세는’ 알고리즘을 말한다.

각 크기에 해당하는 숫자의 개수를 모두 세서, 각 개수만큼 출력하면 정렬한 것과 같아지는 효과를 이용한다.

1. 초기 상태 (초기화)

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

2. 차례로 읽으며 해당 숫자의 개수를 증가

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

3. 마지막 번호까지 모두 읽어 해당 숫자의 개수를 증가

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

4. 각 숫자의 개수 만큼 출력

1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5

Source Code

#include <stdio.h>

int main (void) {
	int temp, i, j;
	int count[5];
	int array[30] = {
		1,3,2,4,3,2,5,3,1,2,
		3,4,4,3,5,1,2,3,5,2,
		3,1,4,3,5,1,2,1,1,1
	};
	
	for(i = 0; i < 5; i++) { // init array with 0
		count[i] = 0;
	}
	for(i = 0; i < 30; i++) { // count nums
		count[array[i] - 1]++;
	}
	for(i = 0; i < 5; i++) { // print array
		if(count[i] != 0) {
			for(j = 0; j < count[i]; j++)
				printf("%d ", i + 1);
		}
	}
	return 0;	
}

시간 복잡도

이번 계수 정렬은 ‘크기 기준’으로 갯수만 세면 되기 때문에 위치를 바꿀 필요가 없다.

또한 모든 데이터에 한 번씩만 접근하면 된다는 점에서 무척이나 효율적이다.

하지만, 정렬할 데이터 자체의 크기에 큰 영향을 받는다. 데이터를 담을 배열도 커지기 때문이다.

따라서 특정 조건을 만족할 경우에만 주로 효율적인 이용을 위해 사용된다.

계수 정렬의 시간 복잡도는 : O(N)이다.

깃허브