기수 정렬(Radix Sort)은 비교 연산을 사용하지 않는 정렬 알고리즘입니다. 이 알고리즘은 정수 키를 대상으로, 같은 자릿수 위치에 같은 값을 가진 숫자들을 그룹으로 묶는 방식으로 동작합니다. 여기서 말하는 '기수(radix)'란 수 체계의 밑(base)을 뜻하며, 우리가 일상적으로 사용하는 10진법에서 기수는 10입니다. 따라서 10진수를 정렬할 때에는 숫자를 임시로 보관할 10개의 버킷(포켓)이 필요합니다.
기수 정렬의 복잡도
- 시간 복잡도: O(nk) — n은 데이터 개수, k는 최대 자릿수
- 공간 복잡도: O(n+k)
입력과 출력
입력: 정렬되지 않은 리스트: 802 630 20 745 52 300 612 932 78 187 출력: 정렬 전 데이터: 802 630 20 745 52 300 612 932 78 187 정렬 후 데이터: 20 52 78 187 300 612 630 745 802 932
알고리즘 동작 원리
기수 정렬은 가장 낮은 자릿수(LSD, Least Significant Digit)부터 시작하여 각 자릿수를 기준으로 안정 정렬(stable sort)을 반복 적용합니다. 모든 자릿수에 대해 이 과정을 마치면 배열 전체가 오름차순으로 정렬됩니다.
- 현재 자릿수의 숫자(0~9)를 기준으로 각 요소를 해당 번호의 버킷에 분배합니다.
- 버킷 번호 순서대로(0 → 9) 요소를 꺼내 배열에 다시 저장합니다.
- 다음 자릿수(10의 자리, 100의 자리 …)에 대해 같은 과정을 반복합니다.
- 최대 자릿수(maxDigit)만큼 반복하면 정렬이 완료됩니다.
알고리즘
radixSort(array, size, maxDigit)
입력 − 데이터 배열, 배열의 총 데이터 수, 최댓값의 자릿수
출력 − 정렬된 배열
Begin
define 10 lists as pocket
for i := 0 to max -1 do
m = 10^i+1
p := 10^i
for j := 0 to n-1 do
temp := array[j] mod m
index := temp / p
pocket[index].append(array[j])
done
count := 0
for j := 0 to radix do
while pocket[j] is not empty
array[count] := get first node of pocket[j] and delete it
count := count +1
done
done
End
C++ 구현 예제
#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void radixSort(int *arr, int n, int max) {
int i, j, m, p = 1, index, temp, count = 0;
list<int> pocket[10]; // 10진수의 기수(radix)는 10
for(i = 0; i<max; i++) {
m = pow(10, i+1);
p = pow(10, i);
for(j = 0; j<n; j++) {
temp = arr[j]%m;
index = temp/p; // 포켓 배열의 인덱스 계산
pocket[index].push_back(arr[j]);
}
count = 0;
for(j = 0; j<10; j++) {
// 연결 리스트에서 제거하고 배열에 다시 저장
while(!pocket[j].empty()) {
arr[count] = *(pocket[j].begin());
pocket[j].erase(pocket[j].begin());
count++;
}
}
}
}
int main() {
int n, max;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter the maximum digit of elements: ";
cin >> max;
int arr[n]; // 입력받은 개수만큼 배열 생성
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Data before Sorting: ";
display(arr, n);
radixSort(arr, n, max);
cout << "Data after Sorting: ";
display(arr, n);
}
실행 결과
Enter the number of elements: 10 Enter the maximum digit of elements: 3 Enter elements: 802 630 20 745 52 300 612 932 78 187 Data before Sorting: 802 630 20 745 52 300 612 932 78 187 Data after Sorting: 20 52 78 187 300 612 630 745 802 932
실행 결과에서 확인할 수 있듯이, 기수 정렬은 요소 간 크기를 직접 비교하지 않고도 자릿수 단위의 분배와 수집 과정만으로 배열을 정렬합니다. 데이터 개수 n에 비해 최대 자릿수 k가 작은 정수 데이터를 다룰 때 특히 효율적인 알고리즘입니다.