계수 정렬(카운팅 정렬) 개념, 분석, 활용

계수 정렬(카운팅 정렬)이란?

계수 정렬은 특정 범위에 있는 값을 정렬하는 정렬 기법입니다. 각 값의 개수를 셉니다.

 

계수 정렬은 복잡도가 굉장히 낮습니다.

시간 복잡도는 무려 O(n+k). (n: 나열된 요소 개수 e.g. 5개, k: 입력의 범위 [가장 큰 요소 - 가장 작은 요소])

공간 복잡도도 무려 O(K)가 됩니다.

 

아주 빠른 배열임에도 불구하고 음수인 요소에 대해서는 정렬할 수 없다는 단점이 있습니다. 음수 인덱스는 없기 때문입니다.

계수 정렬 예시를 통한 이해

아래 예시로 한번에 이해하도록 해 보겠습니다.

1) 1 3 2 4 5 1 1를 나열해야 합니다.

2) 우리는 나열된 숫자의 범위가 1~5 안에 있다는 것을 알고 있습니다.

3) 배열을 선언합니다. int arr[5];로 선언합니다.

이 때 5는 숫자의 범위만큼 개수를 선언합니다. 1~5 범위이므로 5개가 됩니다.

4) 하나씩 세어 봅니다. 그리고 배열에 담습니다.

1 3 2 4 5 1 1

첫 번째 숫자는 1이므로, arr[0]에 담습니다. (가장 첫 번째 인덱스에 담습니다.)

 

1 3 2 4 5 1 1

두 번째 숫자는 3이므로, arr[2]에 담습니다.

 

1 3 2 4 5 1 1

세 번째 숫자는 2이므로, arr[1]에 담습니다.

...

 

1 3 2 4 5 1 1

첫 번째 숫자는 2이므로, arr[0]에 담습니다. 위에 이미 1이 하나 있었으므로 이 때 배열 내의 값을 하나 올려줍니다.

 

즉, 인덱스는 나열된 값이고, 배열 내의 값은 그 값의 개수가 됩니다.

 

그럼 이 배열을 이제 어떻게 활용할 수 있을까요?

1~5 범위에서 나열된 숫자를 오름 차순으로 정렬하는 코드 예시를 살펴 보겠습니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int count[5]={}; // 카운팅 정렬 배열. 인덱스는 나열된 값이고 배열 내의 값은 개수가 됨. 

int main(void)
{
	int num=0;
	int arr[7]={1,3,2,4,5,1,1}; // 정렬 대상 요소 
	
	for (int i = 0; i<7; i++)
	{
		num=arr[i];
		count[num-1]++;
	}
	
	for (int i = 0; i<7; i++)
	{
		if (count[i]!=0) // 배열 내 값이 0 인 경우 개수가 0이라는 의미이므로 무시 
		{
			for (int j = 0; j<count[i]; j++)
			{
				printf("%d\n", i+1);
			}
		}
	}
	
	return 0;
}