[Algorithm] Counting Sort, 계수 정렬
이번 포스팅에서는 Counting Sort 에 대해서 알아보도록 하겠습니다.
Counting Sort의 동작원리, 시간복잡도, C++로 구현한 코드를 보며 이해해보겠습니다.
동작원리
다음과 같이 origin이라는 배열을 Counting Sort를 통해서 정렬 해보도록 하겠습니다.
int origin[] = {5, 3, 4, 5, 1, 0, 4, 1, 3, 0, 2, 4, 2, 3, 0};
Counting
첫 번째로 해야할 일은 각 숫자가 몇 번 나왔는지 세야합니다.
origin 배열에 등장한 수와 그 수가 몇 번 나왔는지를 기재하였습니다.
| 수 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 나온 횟수 | 3 | 2 | 2 | 3 | 3 | 2 |
Counting Sum
다음으로는 각 수의 누적합을 구해줍니다. 누적합을 통해서 해당 숫자가 어느 인덱스에 위치해야 하는지를 찾을 수 있습니다.
| 수 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 나온 횟수 | 3 | 2 | 2 | 3 | 3 | 2 |
| 횟수에 대한 누적합 | 3 | 5 | 7 | 10 | 13 | 15 |
Sorting
이제 위에 만든 배열을 통해 정렬된 배열을 만들어봅시다.
정렬된 배열을 만드는 과정은 아래와 같습니다.
- origin 배열을 뒤에서 앞으로 순회합니다.
- origin[i] 값의 누적합에 해당하는 위치에 값을 대입합니다.
- origin[i] 값이 하나 없어졌으므로 해당 값에 대한 누적합을 1 감소합니다.
- 2번과 3번을 반복합니다.
위에 예시에 대해 일부 과정을 함께 진행해보겠습니다.
[origin]
| 인덱스 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 수 | 5 | 5 | 3 | 4 | 5 | 1 | 0 | 4 | 1 | 3 | 0 | 2 | 4 | 3 | 0 |
배열을 뒤에서 부터 앞으로 순회하기 때문에 인덱스 15인 0부터 시작합니다.
0에 대한 누적합은 3이었으므로 인덱스 3에 0을 대입합니다.
[answer]
| 인덱스 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 수 | 0 |
다음으로 0이 등장하였을 때는 인덱스 2에 대입해야합니다. 그러기 위해 누적합을 1 감소시킵니다.
| 수 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 나온 횟수 | 3 | 2 | 2 | 3 | 3 | 2 |
| 횟수에 대한 누적합 | 2 | 5 | 7 | 10 | 13 | 15 |
origin 배열에서 14번째 인덱스의 수는 3입니다.
3의 누적합은 10이므로 answer 10에 3을 넣어주고 누적합을 1 감소시킵니다.
[answer]
| 인덱스 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 수 | 0 | 3 |
| 수 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 나온 횟수 | 3 | 2 | 2 | 3 | 3 | 2 |
| 횟수에 대한 누적합 | 2 | 5 | 7 | 9 | 13 | 15 |
다음 과정을 반복하면 모든 표를 다 채울 수 있습니다.
| 인덱스 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 수 | 0 | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 5 | 5 |
시간 복잡도
이번에는 Counting Sort, 계수 정렬의 시간복잡도를 알아봅시다.
기타 정렬들과 다르게 특이한 시간복잡도를 가집니다.
배열의 크기를 n, 가장 큰 수를 k라고 하면 계수 정렬의 시간 복잡도는 O(n+k) 입니다.
각각의 수가 몇 개 나왔는지 세는 과정, origin 배열을 역으로 순회하는 과정이 모두 O(n)입니다.
그리고 누적합을 구하는 과정이 O(k)가 됩니다.
따라서 k가 n보다 작다는 것이 보장된 경우, O(n)의 시간복잡도로 다른 정렬 알고리즘에 비해 높은 효율을 보입니다.
하지만 k가 n보다 크다면 기간 복잡도는 얼마나 될 지 예측할 수 없습니다.
C++ 구현
위에서 설명한 내용 그대로 C++로 구현을 하였습니다.
#include <iostream>
#define MAX_SIZE 1000
#define MAX_NUM 10000
using namespace std;
int main()
{
int N;
int origin[MAX_SIZE + 1];
int answer[MAX_SIZE + 1];
int count[MAX_NUM + 1];
int count_sum[MAX_NUM + 1];
cin >> N;
for (int i = 0; i <= N; i++)
count[i] = 0;
// Counting
for (int i = 1; i <= N; i++)
{
cin >> origin[i];
count[origin[i]]++;
}
// Counting Sum
count_sum[0] = count[0];
for (int i = 1; i <= MAX_NUM; i++)
count_sum[i] = count_sum[i - 1] + count[i];
// Sorting
for (int i = N; i >= 1; i--)
{
answer[count_sum[origin[i]]] = origin[i];
count_sum[origin[i]]--;
}
for (int i = 1; i <= N; i++)
cout << answer[i] << " ";
}