기수 정렬(Radix Sort)이란?
정렬 알고리즘(sorting algorithm)은 리스트의 요소들을 특정한 순서대로 배열하는 알고리즘입니다. 가장 널리 사용되는 순서는 수치적 순서(numerical order)와 사전식 순서(lexicographic order)입니다.
기수 정렬(Radix Sort)은 요소 간 비교를 수행하지 않는 비비교(non-comparative) 정렬 알고리즘으로, 정렬되지 않은 리스트를 처리할 때 가장 선호되는 알고리즘 중 하나입니다.
기수 정렬은 동일한 자릿수(place value)를 가진 숫자끼리 그룹화하는 방식으로 요소를 정렬합니다. 핵심 아이디어는 최하위 자릿수(LSD, Least Significant Digit)부터 최상위 자릿수(MSD, Most Significant Digit)까지 자릿수 단위로, 오름차순 또는 내림차순 순서에 따라 차례대로 정렬하는 것입니다.
기수 정렬은 대량의 이름 목록을 알파벳순으로 정렬할 때 여러 번 활용되는 간단하고 실용적인 방법이기도 합니다. 구체적으로, 이름 목록은 먼저 각 이름의 첫 글자를 기준으로 정렬되며, 이 과정에서 이름들이 총 26개의 범주(A~Z)로 분류됩니다.
기수 정렬의 동작 원리
다음 그림을 통해 기수 정렬 알고리즘이 실제로 어떻게 작동하는지 명확하게 이해해 보겠습니다. 정렬 패스(pass), 즉 반복 횟수는 입력 값 중 가장 큰 숫자의 자릿수 크기에 따라 결정됩니다.
위 예제에서 첫 번째 열은 입력값을 나타내며, 나머지 열들은 낮은 자릿수부터 높은 자릿수 순으로 연속적으로 정렬을 수행한 이후의 리스트 상태를 보여줍니다.
기수 정렬의 시간 복잡도
기수 정렬의 시간 복잡도는 O(m·n)입니다. 여기서 m은 키(key)의 자릿수 길이, n은 키의 개수를 의미합니다.
그러나 두 값을 함께 살펴보면, 키의 크기는 키의 개수에 비해 상대적으로 매우 작다는 것을 알 수 있습니다. 예를 들어 6자리 키를 사용한다면, 서로 다른 레코드는 최대 1,000,000개까지 존재할 수 있습니다.
결국 키의 크기는 성능에 큰 영향을 주지 않으므로, 기수 정렬은 사실상 선형 시간 복잡도 O(n)의 성능을 가지는 알고리즘이라고 할 수 있습니다.
알고리즘 의사 코드(Pseudocode)
Radix_sort (list, n)
shift = 1
for loop = 1 to keysize do
for entry = 1 to n do
bucketnumber = (list[entry].key / shift) mod 10
append (bucket[bucketnumber], list[entry])
list = combinebuckets()
shift = shift * 10
C 언어 구현 예제
다음은 기수 정렬을 C 언어로 구현한 프로그램입니다. 먼저 get_max() 함수로 배열 내 최댓값을 찾아 자릿수(패스 횟수)를 계산하고, 각 패스마다 10개의 버킷(bucket)에 요소를 분배한 뒤 다시 합치는 방식으로 정렬을 진행합니다.
#include<stdio.h>
int get_max (int a[], int n){
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void radix_sort (int a[], int n){
int bucket[10][10], bucket_cnt[10];
int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
lar = get_max (a, n);
while (lar > 0){
NOP++;
lar /= 10;
}
for (pass = 0; pass < NOP; pass++){
for (i = 0; i < 10; i++){
bucket_cnt[i] = 0;
}
for (i = 0; i < n; i++){
r = (a[i] / divisor) % 10;
bucket[r][bucket_cnt[r]] = a[i];
bucket_cnt[r] += 1;
}
i = 0;
for (k = 0; k < 10; k++){
for (j = 0; j < bucket_cnt[k]; j++){
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
printf ("After pass %d : ", pass + 1);
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
}
}
int main (){
int i, n, a[10];
printf ("Enter the number of items to be sorted: ");
scanf ("%d", &n);
printf ("Enter items: ");
for (i = 0; i < n; i++){
scanf ("%d", &a[i]);
}
radix_sort (a, n);
printf ("Sorted items : ");
for (i = 0; i < n; i++)
printf ("%d ", a[i]);
printf ("\n");
return 0;
}
실행 결과
Enter number of items to be sorted 6
Enter items:567 789 121 212 563 562
After pass 1 : 121 212 562 563 567 789
After pass 2 : 212 121 562 563 567 789
After pass 3 : 121 212 562 563 567 789
Sorted items : 121 212 562 563 567 789
실행 결과를 보면, 1의 자릿수 기준 정렬 → 10의 자릿수 기준 정렬 → 100의 자릿수 기준 정렬 순으로 세 번의 패스를 거치면서 데이터가 최종적으로 오름차순으로 정렬되는 것을 확인할 수 있습니다.