기수 정렬 (Radix Sort)
들어가는 말
기수(基數, radix)는 한 자릿수에서 사용할 수 있는 숫자의 개수로, 10진수의 기수는 10이고 2진수의 기수는 2이다.
기수 정렬은 값을 직접 비교하지 않고 각 자릿수를 기준으로 정렬하는 비(非)비교 정렬이다.
각 자릿수를 기준으로 정렬하는 방법은 다양하다.
자릿값마다 큐를 두고 원소를 분배한 뒤 다시 모을 수도 있고, 계수 정렬로 각 원소가 들어갈 위치를 계산해 출력 배열에 배치할 수도 있다.
기수 정렬에는 가장 낮은 자릿수부터 정렬하는 LSD(Least Significant Digit) 방식과 가장 높은 자릿수부터 정렬하는 MSD(Most Significant Digit) 방식이 있다.
이 글에서는 음수가 없는 10진수 정수의 자릿수를 LSD 방식으로 순회하고, 각 자릿수는 계수 정렬로 정렬한다.
정렬 과정 살펴보기
다음 15개의 원소를 오름차순으로 정렬해 보자.
73 4 28 91 6 145 32 8 57 20 3 84 61 209 45
가장 큰 값은 209이고 세 자리 수이므로 일의 자리부터 백의 자리까지 총 3회차를 진행한다.
어떤 값에 현재 자릿수가 없다면 해당 자릿수를 0으로 취급한다.
현재 자릿수는 다음 코드로 구할 수 있다.
(209 / 1) % 10; // 9
(209 / 10) % 10; // 0
(209 / 100) % 10; // 2
digit = (value / place_value) % 10;place_value는 일의 자리에서 1, 십의 자리에서 10, 백의 자리에서 100이다.
1회차: 일의 자리
각 값의 일의 자리를 기준으로 안정적인 계수 정렬을 수행한다.
| 인덱스(자릿값) | 빈도 | 해당 원소 |
|---|---|---|
| 0 | 1 | 20 |
| 1 | 2 | 91, 61 |
| 2 | 1 | 32 |
| 3 | 2 | 73, 3 |
| 4 | 2 | 4, 84 |
| 5 | 2 | 145, 45 |
| 6 | 1 | 6 |
| 7 | 1 | 57 |
| 8 | 2 | 28, 8 |
| 9 | 1 | 209 |
안정 정렬의 중요성은 다음 회차부터 드러난다.
다음 자릿수를 정렬할 때는 자릿값이 같은 원소의 순서를 유지해야 이전 회차에서 정렬한 낮은 자릿수의 순서가 보존된다.
| 정렬 단계 | 배열 상태 |
|---|---|
| 일의 자리 정렬 후 | 20 91 61 32 73 3 4 84 145 45 6 57 28 8 209 |
2회차: 십의 자리
1회차의 결과를 십의 자리를 기준으로 안정적인 계수 정렬한다.
이때 한 자리 수의 십의 자리는 0으로 간주한다.
| 인덱스(자릿값) | 빈도 | 해당 원소 |
|---|---|---|
| 0 | 5 | 3, 4, 6, 8, 209 |
| 1 | 0 | - |
| 2 | 2 | 20, 28 |
| 3 | 1 | 32 |
| 4 | 2 | 145, 45 |
| 5 | 1 | 57 |
| 6 | 1 | 61 |
| 7 | 1 | 73 |
| 8 | 1 | 84 |
| 9 | 1 | 91 |
이 과정에서 안정 정렬의 역할이 드러난다.
십의 자릿값이 0인 3, 4, 6, 8, 209는 같은 자릿값에 해당하면서도 1회차에서 정해진 상대적인 순서를 유지한다.
십의 자릿값이 2인 20과 28도 마찬가지로 20, 28 순서를 유지한다.
| 정렬 단계 | 배열 상태 |
|---|---|
| 십의 자리 정렬 후 | 3 4 6 8 209 20 28 32 145 45 57 61 73 84 91 |
3회차: 백의 자리
2회차의 결과를 백의 자리를 기준으로 안정적인 계수 정렬한다.
이때 한 자리 수와 두 자리 수의 백의 자리는 0으로 간주한다.
| 인덱스(자릿값) | 빈도 | 해당 원소 |
|---|---|---|
| 0 | 13 | 3, 4, 6, 8, 20, 28, 32, 45, 57, 61, 73, 84, 91 |
| 1 | 1 | 145 |
| 2 | 1 | 209 |
| 3 | 0 | - |
| 4 | 0 | - |
| 5 | 0 | - |
| 6 | 0 | - |
| 7 | 0 | - |
| 8 | 0 | - |
| 9 | 0 | - |
백의 자리가 0인 값들은 이전 회차에서 정렬된 3 4 6 8 20 28 32 45 57 61 73 84 91의 순서를 그대로 유지한다.
가장 큰 값의 마지막 자릿수까지 정렬했으므로 전체 배열의 정렬이 끝난다.
| 정렬 단계 | 배열 상태 |
|---|---|
| 백의 자리 정렬 후 | 3 4 6 8 20 28 32 45 57 61 73 84 91 145 209 |
회차별 정렬 과정 요약
| 회차 | 기준 자릿수 | 배열 상태 |
|---|---|---|
| 시작 전 | - | 73 4 28 91 6 145 32 8 57 20 3 84 61 209 45 |
| 1회차 | 일의 자리 | 20 91 61 32 73 3 4 84 145 45 6 57 28 8 209 |
| 2회차 | 십의 자리 | 3 4 6 8 209 20 28 32 145 45 57 61 73 84 91 |
| 3회차 | 백의 자리 | 3 4 6 8 20 28 32 45 57 61 73 84 91 145 209 |
안정 정렬이 필요한 이유
LSD 방식은 낮은 자릿수에서 정렬한 결과를 유지한 채 더 높은 자릿수를 정렬해야 한다.
예를 들어 일의 자리 정렬에서 20은 28보다 먼저 배치되며, 두 값의 십의 자리가 모두 2이므로 십의 자리 정렬에서도 이 순서를 유지해야 한다.
더 높은 자릿수를 정렬할 때 같은 자릿값을 가진 원소의 순서가 뒤바뀌면 앞선 회차에서 정렬한 결과가 사라진다.
따라서 현재 자릿값이 같은 원소의 상대적인 순서를 보존하는 안정 정렬을 사용해야 한다.
시간 복잡도
원소의 개수를 n, 가장 큰 값의 자릿수를 d, 한 자릿수가 가질 수 있는 값의 개수를 k라고 하자.
10진수에서는 각 자릿수가 0부터 9까지이므로 k는 10이다.
한 자릿수를 기준으로 계수 정렬할 때 원소를 세는 데 O(n), 누적 합을 구하는 데 O(k), 출력 배열을 만드는 데 O(n)이 걸린다.
따라서 한 회차의 시간 복잡도는 O(n + k)이다.
이 과정을 가장 큰 값의 자릿수만큼 d번 반복하므로 전체 시간 복잡도는 이다.
기수 정렬은 원소의 크기를 직접 비교하지 않으므로 비교 기반 정렬의 하한인 보다 빠르게 동작할 수 있다.
다만 값의 자릿수가 많으면 반복 횟수가 늘어나고, 정수 이외의 자료는 자릿수의 추출 및 저장 방식을 별도로 설계해야 하므로 범용성에 제약이 있다.
보조 배열에 n개의 원소를 저장하고 각 자릿값의 개수를 저장하는 배열에 k개의 원소를 사용하므로 공간 복잡도는 O(n + k)이다.
소스 코드
#include <stdio.h>
#include <stdlib.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_by_digit(int arr[], int temp[], int size, long long place_value)
{
int digit_counts[10] = { 0 };
for (int i = 0; i < size; i++)
{
int digit = (arr[i] / place_value) % 10;
digit_counts[digit]++;
}
for (int i = 1; i < 10; i++)
{
digit_counts[i] += digit_counts[i - 1];
}
for (int i = size - 1; i >= 0; i--)
{
int digit = (arr[i] / place_value) % 10;
temp[digit_counts[digit] - 1] = arr[i];
digit_counts[digit]--;
}
for (int i = 0; i < size; i++)
{
arr[i] = temp[i];
}
}
void radix_sort(int arr[], int size)
{
int max = get_max(arr, size);
long long place_value = 1;
int* temp = malloc(sizeof(int) * size);
if (temp == NULL)
{
return;
}
while (place_value <= max)
{
counting_sort_by_digit(arr, temp, size, place_value);
place_value *= 10;
}
free(temp);
}
int main(void)
{
int arr[] = { 73, 4, 28, 91, 6, 145, 32, 8, 57, 20, 3, 84, 61, 209, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
radix_sort(arr, size);
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]); // Result: 3 4 6 8 20 28 32 45 57 61 73 84 91 145 209
}
return 0;
}구현 설명
counting_sort_by_digit은 현재 자릿수를 기준으로 안정적인 계수 정렬을 수행한다.
계수 정렬에서 설명했으므로, 여기서는 radix_sort의 반복 구조를 중심으로 살펴본다.
place_value는 현재 정렬할 자릿수를 나타내며 일의 자리인 1에서 시작해 회차마다 10배씩 증가한다.
while 문의 조건식 place_value <= max는 현재 자릿수가 가장 큰 값의 자릿수 범위 안에 있는지 확인한다.
예를 들어 max가 209이면 place_value가 1, 10, 100일 때 반복문을 실행하여 일의 자리부터 백의 자리까지 정렬한다.
백의 자리를 정렬한 뒤 place_value가 1,000이 되면 조건식이 거짓이므로 반복문을 종료한다.
place_value를 int로 선언하면 가장 높은 자릿수를 처리한 뒤 10을 곱하는 과정에서 표현 범위를 벗어날 수 있다.
예를 들어 32비트 int에서 place_value가 1,000,000,000이면 다음 값인 10,000,000,000은 최댓값 2,147,483,647을 초과한다.
이 코드에서는 place_value를 더 큰 정수 범위를 가지는 long long으로 선언하여 오버플로우를 방지한다.
덕분에 별도의 오버플로우 검사 없이 place_value <= max라는 하나의 조건만으로 반복 여부를 판단할 수 있다.