기수정렬(Radix sort)

비-비교정렬로서 낮은 자리수 부터 비교하여 정렬해 간다는 것을 기본으로 한다.

시간복잡도는 O(d*n) : n은 데이터의 개수, d는 가장 큰 데이터의 자리수 이다.

0 보다 크거나 같은 정수를 정렬하는 코드를 첨부한다.

수도코드를 참고한 것이 아니다. 그러므로 코드가 상이할 수 있다.

가장 작은 자릿수부터 넣고 다시 꺼내어 하나 더 높은 자릿수를 넣고, 이 과정이 끝날 때까지 정렬한다는 생각으로 코드를 작성했다.

1. 가장 작은 자릿수부터 [0,9] 에 해당하는 값을 구한다.
   1. 구한 값에 해당하는 위치에 radix[자릿수] 에 값을 추가한다.
   2. 모든 값을 추가하고 radix[0]부터 radix[9] 순서로 먼저 값을 넣은 것부터 꺼내어 자릿수로 정렬된 수열을 꺼낸다.
   3. 주어진 수열에서 가장 큰 값보다 구할 자릿수 값이 커진 경우 종료한다.
   4. 다음으로 큰 자릿수를 구한다. 1-1을 다시 진행한다.

#include<iostream>
#include<vector>
using namespace std;
typedef vector<int> vi;
 
vi radix_sort(vi v, int mx) {
    int rem = 10;
    bool ok = false;
    vi radix[10];
    while (!ok) {
        int num_ok = 0;
        for (int i = 0; i < 10; i++) {
            radix[i].clear();
        } // radix init
 
        for (int i = 0; i < v.size(); i++) {
            int here = (v[i] % rem) / (rem / 10);
            radix[here].push_back(v[i]);
        }
        
        v.clear();
 
        for (int i = 0; i < 10; i++) {
            for (auto it : radix[i]) {
                v.push_back(it);
            }
        }
 
        if (rem > mx) ok = true;
        else rem *= 10;
    }
    return v;
} // radix sort
int main() {
    int n;
    cin >> n;
    vi numbers = vi(n, -1);
    int mx = -1;
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
        if (mx < numbers[i]) mx = numbers[i];
    }
 
    vi ret = radix_sort(numbers, mx);
    for (auto it : ret) {
        cout << it << endl;
    }
    return 0;
}
 
/* input
7
102 54 524 13 2 1 0
*/