[알고리즘] 계수 정렬

선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 중 가장 빠른 알고리즘은

당연히 퀵 정렬, 병합 정렬, 힙 정렬 중 하나일 것이다.

​

하지만 '범위 조건' 이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있다.

그것은 바로 계수 정렬이다.

​

계수 정렬 : 단순하게 ' 크기를 기준으로 ' 세는 알고리즘

​

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 즉 5이하의 자연수 데이터들을 오름차순으로 정렬할 때

​

크기를 기준으로 정렬하기 때문에

크기 : 1 = 0 크기 : 2 = 0 크기 : 3 = 0 크기 : 4 = 0 크기 : 5 = 0

​

여기에서

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의 첫번 째 상태는

크기 : 1 = 1 크기 : 2 = 0 크기 : 3 = 0 크기 : 4 = 0 크기 : 5 = 0

​

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의 두번 째 상태는

크기 : 1 = 1 크기 : 2 = 0 크기 : 3 =1 크기 : 4 = 0 크기 : 5 = 0

​

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의 세번 째 상태는

크기 : 1 = 1 크기 : 2 = 1 크기 : 3 =1 크기 : 4 = 0 크기 : 5 = 0

​

...

​

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의 마지막 상태는

크기 : 1 = 8 크기 : 2 = 6 크기 : 3 =8 크기 : 4 = 4 크기 : 5 = 4

​

이렇게 크기를 기준으로 정렬을 완료하고

​

1 ~ 5까지 해당 숫자만 큼 출력하면 된다. = > 1은 8번, 2는 6번, 3은 8번, 4는 4번, 5는 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

​

이렇게 범위를 제시하고 ' 크기를 기준' 으로 정렬을 하였다.

​

이 방법의 시간 복잡도는 무려 O(N)이라는 어마무시한 속도를 자랑한다.

​

계수 정렬의 시간 복잡도

O(N)

 

#include<stdio.h>

#define num 30

int data[num] = { 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 };
int sort[5];   // 값의 범위가 1 ~ 5이기 때문

int main(void) {   // 계수 정렬
	for (int i = 0; i < num; i++) {

		sort[data[i]-1] ++;
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < sort[i]; j++)
			printf("%d ", i + 1);
	}
}

N번만 연산을 수행하기 때문에 코드도 간결하다!

모든 데이터의 크기 범위를 표현이 가능하다면 O(N)이라는 압도적인 속도로 정렬을 수행할 수 있다!