[알고리즘] 기수 정렬(Radix Sort)

이번 시간에는 기수정렬(Radix Sort)에 대해 공부해 보겠습니다. 개인적으로 기수 정렬을 배우면서 이런 방법으로도 정렬할 수 있구나, 라는 생각을 했고 굉장히 신선했습니다.

 

기수정렬은 각 숫자의 일의 자리, 십의 자리, 백의 자리....를 기준으로 숫자를 정렬하는 방법입니다. 이때 각 기준숫자는 0~9 범위에 포함되는데 이를 관리하기 위해 0 ~ 9, 총 10개의 queue를 만들어 줍니다.

 

[200, 152, 2, 0, 32, 45, 99, 87] 를 한번 보겠습니다.

 

1. 일의 자리를 기준으로 정렬

이를 배열로 다시 표현해보겠습니다. 0에서 부터 시작하며 queue이기 때문에 선입선출 입니다.

[200, 0, 152, 2, 32, 45, 87, 99]

 

2. 십의 자리를 기준으로 정렬

일의 자리를 기준으로 정렬한 값을 다시 십의 자리를 기준으로 정렬하면 다음과 같습니다.

[200, 0, 2, 32, 45, 152, 87, 99]

 

3. 백의 자리를 기준으로 정렬

십의 자리를 기준으로 정렬한 값을 다시 백의 자리를 기준으로 정렬하면 다음과 같습니다.

[0, 2, 32, 45, 87, 99, 152, 200]

 

기수정렬의 시간복잡도는 O(d(n+k)) 입니다. 여기서 n은 입력 데이터의 개수, d는 정수 중 가장 큰 자릿수 입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int main(){

    int arr[8] = {200,152,2,0,32,45,99,87 };
    queue<int> radix[10]; 
    int max = 0;                  // 최대값을 구함

    for(int i=0;i<8;i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }

    int maxPos = 1;              // 최대값이 몇번째 자리인지 ?  (4자리면 1000, 3자리면 100, 2자리면 10, 1자리면 1)    
    while(max > 10){             // maxPos값을 구하는 과정
        maxPos = maxPos * 10;
        max = max / 10;
    }

    int pos = 1;                 
    int mod = 10;
    
    while(pos <= maxPos){
        for(int i=0;i < 8;i++){
            radix[(arr[i] % mod ) / pos].push(arr[i]);   // 각 숫자는 기준위치의 값을 queue에 넣음
        }

        for(int i=0, j=0; i<10;){
            if(radix[i].size()){                        // que에 값이 비어있으면 pass
                arr[j++] = radix[i].front();
                radix[i].pop();
            }else{
                i++;
            }
        }

        mod = mod * 10;
        pos = pos * 10;
        
         for(int i=0;i<8;i++){
              cout << arr[i] << " ";
         }cout << "\n";
    }


    return 0;
}