기수 정렬(Radix Sort)
기본 개념
•
비교 연산을 수행하지 않고, 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘
•
데이터의 각 자릿수를 낮은 자리수부터 가장 큰 자리수까지 차례대로 올라가며 정렬
•
기수만큼의 추가적인 버킷 저장 공간이 필요하다.
원리
1.
현재 데이터들 중 가장 큰 자릿수를 파악한다
2.
각 데이터들의 1의 자리를 비교해서 오름차순으로 정렬한다
3.
그 다음 10의 자릿수를 오름차순으로 정렬한다.
4.
3번 과정에서 만약 10의 자리가 없다면 0으로 간주하여 가장 앞으로 보낸다.
5.
위의 과정을 가장 큰 자릿수까지 반복한다.
예시)
•
현재 데이터들 중 가장 큰 자릿수는 100 자릿수이다.
•
1의 자릿수부터 비교하여 버킷에 오름차순으로 정렬한다.
•
만약 동일 자릿수가 존재한다면, 원래 배열에 담긴 순으로 정렬한다.
•
10의 자릿수를 기준으로 비교하여 오름차순으로 정렬한다.
•
만약 10의 자릿수가 없다면, 가장 앞으로 옮기고, 원래 있던 데이터의 뒤에 추가한다.
•
마지막으로 100의 자릿수를 기준으로 정렬하면 정렬된 배열을 얻을 수 있다.
알고리즘
#include <iostream>
#include <cstdlib>
#include <ctime>
#define MAX_QUEUE 101
#define ARR_SIZE 20
using namespace std;
template <typename T>
class Queue {
public:
T arr[MAX_QUEUE];
int f = 0, r = 0;
T front() { return arr[f]; }
bool isEmpty() { return (f == r); }
bool isFull() { return ((r + 1) % MAX_QUEUE == f); }
int size() { return (f > r ? f-r : r-f); }
void enqueue(T element) {
arr[r++] = element;
r %= MAX_QUEUE;
}
void dequeue() { f = (f + 1) % MAX_QUEUE; }
};
int get_digit(int n, int digit) {
int div = 1;
for (int i = 0; i < digit; i++) {
div *= 10;
}
n /= div;
return (n % 10);
}
void radix_sort(int *arr, int size) {
Queue<int> q[10];
int maxNum = 0, maxDigits = 0;
for (int i = 0; i < size; i++) {
if (maxNum < arr[i]) maxNum = arr[i];
}
while (maxNum != 0) {
maxDigits++;
maxNum /= 10;
}
for (int i = 1; i <= maxDigits; i++) {
for (int j = 0; j < size; j++) {
q[get_digit(arr[j], i)].enqueue(arr[j]);
}
int arrIdx = 0;
for (int j = 0; j < 10; j++) {
while (!q[j].isEmpty()) {
arr[arrIdx++] = q[j].front();
q[j].dequeue();
}
}
}
}
int main() {
int arr[ARR_SIZE];
srand(time(NULL));
for (int i = 0; i < ARR_SIZE; i++) {
arr[i] = (rand() % 100000) + 1;
}
cout << "Before Radix Sort\n";
for (int i = 0; i < ARR_SIZE; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
radix_sort(arr, ARR_SIZE);
cout << "After Radix Sort\n";
for (int i = 0; i < ARR_SIZE; i++) {
cout << arr[i] << " ";
}
cout << '\n';
return 0;
}
C++
복사
/* 출력
Before Radix Sort
58348 71879 3183 28945 90127 5109 2691 98511 30534 7800 59189 63599 28988 57092 47585 77722 69425 3153 9375 92409
After Radix Sort
2691 3153 3183 5109 7800 9375 28945 28988 30534 47585 57092 58348 59189 63599 69425 71879 77722 90127 92409 98511
*/
C++
복사
장점
•
자릿수를 비교해서 정렬하는 방식이기에 문자열, 정수 정렬이 가능하다.
•
같은 두 수가 있어도 순서가 섞이지 않는 안정 정렬이다.
•
속도가 빠르다.
•
시간복잡도는 O(dN)이다 (N : 데이터의 개수, d: 최대 자릿수)
단점
•
자릿수가 없는 것은 정렬할 수가 없다 (소수 불가)
•
중간 결과를 저장하는 버킷 공간이 필요하다.
•
버킷의 크기를 모든 케이스에 딱 맞게 정의하기 어렵다