계수 정렬 (Counting Sort)
들어가는 말
계수 정렬은 원소를 서로 비교하지 않는 비(非)비교 정렬이다.
각 값이 몇 번 등장하는지 센 뒤 그 결과를 이용해 원소를 순서대로 배치한다.
여기서 계수는 문자 앞에 곱해진 상수를 뜻하는 계수(係數)가 아니라, 각 값이 몇 번 등장했는지를 뜻하는 계수(計數)다.
계수 정렬은 값의 범위가 제한된 경우 비교 정렬보다 빠를 수 있으며, O(n + k)의 시간 복잡도로 동작한다.
계수 정렬은 기수 정렬에서 각 자릿수를 안정적으로 정렬하는 데 사용되기도 한다.
이 글에서는 음수가 없는 정수를 오름차순으로 정렬하는 안정적인 계수 정렬을 살펴본다.
정렬 과정 살펴보기
4 2 2 8 3 3 1을 오름차순으로 정렬해 보자.
1단계: 각 값의 빈도 세기
각 값의 빈도를 저장할 배열을 만들어야 한다.
주어진 배열을 살펴보면 최댓값은 8이다.
원소의 값 자체를 인덱스로 활용하므로 최댓값인 8도 인덱스로 사용할 수 있도록 크기 9의 counts 배열을 만든다.
이제 배열을 순회하며 각 값을 인덱스로 삼아 해당 위치에 빈도를 기록한다.
예를 들어 순회 중 읽은 값이 3이면 counts[3]을 하나 증가시킨다.
| 인덱스 | 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|---|---|---|---|---|---|---|---|---|---|
| 빈도 | 0 |
1 |
2 |
2 |
1 |
0 |
0 |
0 |
1 |
완성된 배열은 다음과 같이 해석할 수 있다.
counts[3]의 값이 2라는 것은 값 3이 두 번 등장했다는 뜻이다.
2단계: 누적 합 구하기
counts[3]이 2라는 것은 값 3이 두 번 등장한다는 뜻일 뿐이지 어느 위치인지는 알 수가 없다.
그래서 각 값 이하인 원소의 개수를 구해 각 값이 들어갈 마지막 위치를 알아내야 한다.
앞의 값까지 누적한 원소 수를 현재 값의 빈도에 더하면, 현재 값 이하인 원소의 개수가 된다.
| 인덱스 | 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|---|---|---|---|---|---|---|---|---|---|
| 누적 원소 수 | 0 |
1 |
3 |
5 |
6 |
6 |
6 |
6 |
7 |
counts[3]이 5라는 것은 3 이하인 원소가 총 5개라는 뜻이다.
실제로 최종 정렬 결과에서 3 이하인 원소는 1 2 2 3 3으로, 모두 5개이고 3의 마지막 인덱스는 4이다.
3단계: 정렬 결과 만들기
정렬할 원본 배열은 4 2 2 8 3 3 1이다.
안정 정렬을 위해 원본 배열을 마지막 원소부터 역순으로 순회한다.
2단계에서 구한 누적 원소 수는 개수이므로, 배열 인덱스로 사용하려면 1을 빼야 한다.
원소를 하나씩 가져와 해당 원소의 누적 개수를 1 감소시킨 뒤, 감소한 값을 배치 인덱스로 사용해 temp 배열에 저장한다.
i |
arr[i] |
배치 인덱스 | temp 배열 상태 |
|---|---|---|---|
6 |
1 |
0 |
1 _ _ _ _ _ _ |
5 |
3 |
4 |
1 _ _ _ 3 _ _ |
4 |
3 |
3 |
1 _ _ 3 3 _ _ |
3 |
8 |
6 |
1 _ _ 3 3 _ 8 |
2 |
2 |
2 |
1 _ 2 3 3 _ 8 |
1 |
2 |
1 |
1 2 2 3 3 _ 8 |
0 |
4 |
5 |
1 2 2 3 3 4 8 |
temp 배열이 완성되면 정렬 결과를 원래 배열로 복사한다.
따라서 최종 결과는 1 2 2 3 3 4 8이다.
시간 복잡도와 공간 복잡도
원소의 개수를 n, 최댓값을 k라고 하자.
빈도를 저장할 배열의 인덱스는 0부터 k까지 사용한다.
빈도를 세고 정렬 결과를 만드는 과정은 입력 배열의 크기에 비례하므로 O(n)이 걸린다.
빈도 배열의 누적 합을 구하는 과정은 값의 범위에 비례하므로 O(k)이 걸린다.
따라서 전체 시간 복잡도는 O(n + k)이다.
빈도 배열은 k + 1개의 원소를, 임시 배열은 n개의 원소를 저장하므로 공간 복잡도는 O(n + k)이다.
k가 n과 비슷하거나 더 작으면 시간 복잡도는 O(n)이 되어 비교 정렬보다 유리할 수 있으며, 추가로 사용하는 공간도 O(n) 범위에 머문다.
반면 k가 n보다 매우 크면 시간 복잡도와 공간 복잡도 모두 O(k)에 가까워져 원소 수에 비해 많은 시간과 메모리가 필요하다.
소스 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int get_max(const int arr[], int size)
{
int max = arr[0];
for (int i = 1; i < size; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
void counting_sort(int arr[], int size)
{
int max = get_max(arr, size);
int* counts = malloc(sizeof(int) * (max + 1));
int* temp = malloc(sizeof(int) * size);
memset(counts, 0, sizeof(int) * (max + 1));
for (int i = 0; i < size; i++)
{
counts[arr[i]]++;
}
for (int i = 1; i <= max; i++)
{
counts[i] += counts[i - 1];
}
for (int i = size - 1; i >= 0; i--)
{
int value = arr[i];
int index = --counts[value];
temp[index] = value;
}
for (int i = 0; i < size; i++)
{
arr[i] = temp[i];
}
free(counts);
free(temp);
}
int main(void)
{
int arr[] = { 4, 2, 2, 8, 3, 3, 1 };
int size = sizeof(arr) / sizeof(arr[0]);
counting_sort(arr, size);
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]); // Result: 1 2 2 3 3 4 8
}
return 0;
}