[알고리즘] 계수 정렬 알고리즘 (Counting Sort)

계수 정렬 알고리즘 (Counting Sort)

 

계수 정렬은 반드시 어떠한 범위안에 존재하는 데이터들로 이루어진 데이터 배열에 한하여 데이터의 크기를 기준으로 카운트하여 정렬하는 알고리즘입니다.

 

쉽게 말해 기준이 크기 5이하인 데이터 배열로 정수 1, 4, 4, 2, 3 가 들어있다면 

크기가 1인 것은 1개, 크기가 2인 것은 1개, 크기가 3인 것은 1개, 크기가 4인 것은 2개로 카운트하여 크기가 작은 순, 혹은 큰 순으로 정렬합니다.

 

1   4   5   2   2   4   1   3   5   3

위와 같은 수가 있을 때 수들을 오름차순으로 계수 정렬을 해보겠습니다.

 

1   4   5   2   2   4   1   3   5   3

크기1 | 1

크기2 | 0

크기3 | 0

크기4 | 0

크기5 | 0

 

1   4   5   2   2   4   1   3   5   3

크기1 | 1

크기2 | 0

크기3 | 0

크기4 | 1

크기5 | 0

 

1   4   5   2   2   4   1   3   5   3

크기1 | 1

크기2 | 0

크기3 | 0

크기4 | 1

크기5 | 1

 

1   4   5   2   2   4   1   3   5   3

크기1 | 1

크기2 | 1

크기3 | 0

크기4 | 1

크기5 | 1

 

1   4   5   2   2   4   1   3   5   3

크기1 | 1

크기2 | 2

크기3 | 0

크기4 | 1

크기5 | 1

 

. . .

이 과정을 반복하면 모든 크기가 다음과 같이 카운트 됩니다

크기1 | 2

크기2 | 2

크기3 | 2

크기4 | 2

크기5 | 2

 

이제 크기 순으로 나열하면 다음과 같이 정렬이 확정됩니다.

1   1   2   2   3   3   4   4   5   5

 

알고리즘 구현

// Algorithm Analysis
// 계수 정렬 (Counting Sort) : 범위 내에 있는 데이터를 크기를 기준으로 카운트하여 정렬

#include <stdio.h>

int main() {
	int temp;
	int count[5];
	int arr[10] = { 1, 4, 5, 2, 2, 4, 1, 3, 5, 3 };

	for (int i = 0; i < 5; i++) {
		count[i] = 0;
	}
	for (int i = 0; i < 10; i++) {
		count[arr[i] - 1]++;
	}
	for (int i = 0; i < 5; i++) {
		if (count[i] != 0) {
			for (int j = 0; j < count[i]; j++) {
				printf("%d ", i + 1);
			}
		}
	}
	return 0;
}

 

시간 복잡도 : O(N)

계수 정렬은 데이터들이 반드시 어떠한 범위내에 있는 경우에만 가능하기 때문에 데이터의 위치를 바꾸는 과정이 없으므로 연산 속도가 매우 빠른 알고리즘입니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.