기수 정렬(Radix Sort)

버킷 정렬(bucket sort)라고도 함. 먼저 들어간 숫자들이 먼저 나와야함.(queue)

숫자의 자릿수 값을 비교하는 정렬.

 

LSD(least significant digit)

;가장 낮은 자릿수부터

MSD(most significant digit)

;가장 높은 자릿수부터

 

시간복잡도

k개의 자릿수를 가지기에 O(kn) 이지만

일반적으로 O(n) 로 표현.

#include <queue>
 
#define BUCKETS   10   // 10진수
#define DIGITS    4    // 4자릿수 테스트
void radizSort(int arr[], int n)
{
    queue<int> que[BUCKETS];
    int factor = 1;    
    for (int d = 0; d < DIGITS; d++)
    {
        int i;
        for (i = 0; i < n; i++)    // 데이터들을 자릿수에 따라 큐에 삽입
        {
            que[(arr[i] / factor) % 10].push(arr[i]);
        }
 
        for (int b = i = 0; b < BUCKETS; b++)
        {
            while (!que[b].empty())    // 버킷에서 꺼내어 arr로 합친다.
            {
                arr[i++] = que[b].front();
                que[b].pop();
            }                
        }
        factor *= 10;    // 그 다음 자릿수로 간다(1 > 10 > 100 ... n)
    }
}
 
void test()
{
    int arr[] = {41, 8467, 6334, 6500, 9169, 5724, 1478, 9358, 6962, 4464, 5705};
    radizSort(arr, 11);
    
    // 41 1478 4464 5705 5724 6334 6500 6962 8467 9169 9358 출력
}