기수 정렬(Radix Sort)은 비교 기반이 아닌 정렬 알고리즘입니다. 이 알고리즘은 정수 키를 대상으로, 같은 자릿수와 값을 공유하는 숫자들을 그룹으로 묶는 방식으로 동작합니다. 여기서 '기수(radix)'란 수 체계의 밑(base)을 의미하는데, 우리가 흔히 사용하는 10진법에서는 기수가 10입니다. 따라서 10진수를 정렬하려면 각 자릿값(0~9)을 담을 수 있는 10개의 위치 저장소가 필요합니다.
기수 정렬의 시간 복잡도
시간 복잡도: O(nk) — n은 데이터 개수, k는 최대 자릿수
공간 복잡도: O(n+k)
입력 − 정렬되지 않은 리스트: 802 630 20 745 52 300 612 932 78 187 출력 − 정렬 후 데이터: 20 52 78 187 300 612 630 745 802 932
알고리즘
radixSort(array, size, maxDigit)
입력: 데이터 배열, 배열의 전체 원소 개수, 최댓값의 자릿수
출력: 정렬된 배열
Begin
10개의 리스트를 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]에 array[j] 추가
done
count := 0
for j := 0 to radix do
while pocket[j]가 비어 있지 않으면
pocket[j]의 첫 번째 노드를 꺼내 array[count]에 저장 후 삭제
count := count + 1
done
done
End예제 코드
#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진수의 기수는 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 배열의 인덱스 계산
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 << "원소의 개수를 입력하세요: ";
cin >> n;
cout << "원소의 최대 자릿수를 입력하세요: ";
cin >> max;
int arr[n]; // 입력받은 개수만큼 배열 생성
cout << "원소를 입력하세요:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "정렬 전 데이터: ";
display(arr, n);
radixSort(arr, n, max);
cout << "정렬 후 데이터: ";
display(arr, n);
}실행 결과
원소의 개수를 입력하세요: 10 원소의 최대 자릿수를 입력하세요: 3 원소를 입력하세요: 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