안녕하세요 기린입니다 :)
지금까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 알고리즘에 대해 알아보았는데요
여기서 정렬 속도가 가장 빠른 알고리즘은 퀵 정렬, 병합 정렬, 힙 정렬 등이 시간복잡도 O(N * logN)으로 가장 빠르다고 할 수 있습니다. 하지만 이 보다 더 빠르게 정렬해야 한다면 어떻게 해야할까요?
다음의 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사이에 속한다는 특징이 있습니다. 이처럼 '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있습니다. 시간 복잡도가 무려 O(N)인 계수 정렬 알고리즘이죠. 계수 정렬은 단순하게 '크기를 기준으로' 갯수를 세는 알고리즘입니다.
여태 공부한 정렬 알고리즘들은 정렬을 위해 데이터의 위치를 바꾸어갔다면, 계수 정렬 알고리즘은 '크기를 기준'으로 데이터의 갯수만 세주면 되기 때문에 위치를 바꿀 필요가 없습니다. 또한 모든 데이터에 한 번씩만 접근하면 되므로 매우 효율적입니다.
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의 개수 | 2의 개수 | 3의 개수 | 4의 개수 | 5의 개수 |
| 0 | 0 | 0 | 0 | 0 |
1. 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
| 1의 개수 | 2의 개수 | 3의 개수 | 4의 개수 | 5의 개수 |
| 1 | 0 | 0 | 0 | 0 |
2. 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
| 1의 개수 | 2의 개수 | 3의 개수 | 4의 개수 | 5의 개수 |
| 1 | 0 | 1 | 0 | 0 |
3. 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
| 1의 개수 | 2의 개수 | 3의 개수 | 4의 개수 | 5의 개수 |
| 1 | 1 | 1 | 0 | 0 |
위와 같은 방식으로 해당 크기의 원소를 만나는 경우 해당 크기의 숫자를 1씩 더해가면 됩니다. 끝까지 반복하면 다음과 같이 됩니다.
| 1의 개수 | 2의 개수 | 3의 개수 | 4의 개수 | 5의 개수 |
| 8 | 6 | 8 | 4 | 4 |
이제 크기 1부터 5까지 해당 숫자만큼 출력하면 정렬이 이루어지겠죠 : ]
위와 같이 '크기를 기준'으로 하는 계수 정렬은 굉장히 속도가 빠릅니다. 이를 소스코드로 한번 보시죠
#include <stdio.h>
int main(void) {
int temp;
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
};
// Initialize variables
for (int i = 0; i < 5; i++) {
count[i] = 0;
}
// Counting Sort
for (int i = 0; i < 30; i++) {
count[array[i] - 1]++;
}
// Output
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;
}소스코드 또한 굉장히 간결합니다. 보시면 모든 데이터의 크기가 1부터 5사이라는 점에서 반복문 자체도 1부터 5까지만 반복하는 것을 알 수 있습니다. 모든 데이터의 크기 범위를 메모리 상에 표현할 수 있다면 O(N)이라는 압도적인 속도로 정렬을 수행할 수 있는 것입니다.
계수 정렬(Counting Sort)의 시간 복잡도는 O(N)입니다.
자 그럼 즐거운 코딩하세요 :)
문의: ralla0405@gmail.com
