[정렬] 기수 정렬

서론

이번 글을 포함해 두 개의 글에 걸쳐 앞에 나온 정렬 알고리즘보다 빠르지만 특수한 경우에서만 성립하는 두 개의 정렬 알고리즘을 다룰 것입니다.

작동 방식

이번 글에서 다룰 기수 정렬은 낮은 자리수 부터 비교하여 정렬하는 알고리즘이며, 정수 데이터에서만 성립하는 알고리즘입니다.
기수 정렬은 몇 개의 키를 기준으로 정렬이 진행되는데, 모든 수가 세 자리 수 이하라면 1의 자리, 10의 자리, 100의 자리로 나누어집니다.

170 45 75 90 2 24 802 66 을 기수 정렬을 이용해 정렬을 해봅시다.
먼저, 1의 자리만 보고 정렬을 하되, 1의 자리가 같으면 먼저 나온 것이 앞에 오게 합니다.
170 90 2 802 24 45 75 66 이 나오게 됩니다.
이 수열을 다시 10의 자리에 대해 정렬을 합시다.
2 802 24 25 66 170 75 90 이 됩니다.
마지막으로 100의 자리에 대해 정렬을 하면,
2 24 45 66 75 90 170 802 가 되면서 정렬이 완료됩니다.

구현을 할 때는 자료구조 큐(Queue)를 사용할 것입니다.
정수의 자리 수를 기준으로 큐에 넣어서 꺼내는 방식으로 진행을 합니다.
35 31 55 41 54 49 를 기수 정렬을 할 건데, 그 전에 0번부터 9번까지의 큐를 생성합니다.
그 다음에 1의 자리를 기준으로 큐에 삽입합니다.
1번 큐에는 31, 41
4번 큐에는 54
5번 큐에는 35, 55
9번 큐에는 49
가 들어가 있습니다.
이제 큐에서 차례대로 꺼내면 31 41 54 35 55 49가 되면서 1의 자리를 기준으로 정렬이 됩니다.
이제 10의 자리를 기준으로 큐에 삽입을 하면,
3번 큐에는 31, 35
4번 큐에는 41, 49
5번 큐에는 54, 55
가 들어가게 되고, 순서대로 꺼내면
31, 35, 41, 49, 54, 55 가 나오면서 정렬이 완료됩니다.

구현

#include <stdio.h>
#include <queue>
using namespace std;

const int n = 5;

void radixSort(int arr[]){
    queue<int> q[10]; //각 자리수를 저장할 큐
    int cnt = 1; //최대 길이^10
    int max = arr[0];
    for(int i=1; i<n; i++) max = max>arr[i]?max:arr[i];
    while(max>0){ //최대 길이^10 구하기
        cnt*=10;
        max/=10;
    }
    for(int i=1; i<=cnt; i*=10){ //정렬할 자리수 (1번 for문)

        for(int j=0; j<n; j++){ //해당 큐에 저장 (2번 for문)
            int k = (arr[j]/i) % (i*10);
            q[k].push(arr[j]);
        }

        int idx = 0; //데이터 꺼내기
        for(int j=0; j<10; j++){
            while(!q[j].empty()){
                arr[idx++] = q[j].front();
                q[j].pop();
            }
        }
    }
}

int main(){
    int arr[n] = {32, 74, 12, 84, 70};
    radixSort(arr);
    for(int i=0; i<n; i++) printf("%d ", arr[i]);
}

시간 복잡도 분석

기수 정렬의 시간 복잡도를 분석해봅시다.
먼저 전체 데이터의 최대 값을 구할 때 O(n)이 걸립니다.
최대값이 몇 자리인지 구할 때는 O(log max)가 걸리고, 최대값의 자리를 d라고 합시다.
주석에 1번 for문이라고 적혀 있는 for문은 d번 돌고,
2번 for문이라고 적혀 있는 for문은 n번 돕니다.
최종 시간 복잡도는 O(n + d + dn) = O(dn)이 걸리게 됩니다.