기수 정렬 - 알고리즘카

기수 정렬은 계수 정렬의 아이디어를 큰 키에 적용하는 방법입니다.

큰 int 배열, 예를 들어 원소가 $10^5$개인 배열을 정렬해야 한다고 합시다. 먼저 안정적인 계수 정렬로 앞의 두 바이트를 기준으로(즉, $\lfloor x / 2^{16} \rfloor$를 키로 사용하여) 정렬한 다음, 그 결과로 얻은 수열을 뒤의 두 바이트를 기준으로(즉, $x \bmod 2^{16}$을 키로 사용하여) 정렬할 수 있습니다.

벡터 배열을 이용한 계수 방식의 구현입니다:

const int c = (1<<16);

void radix_sort(vector<int> &a) {
    int n = (int) a.size();
    vector<int> b[c];

    for (int i = 0; i < n; i++)
        b[a[i] % c].push_back(a[i]);
    
    int k = 0;
    for (int i = 0; i < c; i++) {
        for (size_t j = 0; j < b[i].size(); j++)
            a[k++] = b[i][j];
        b[i].clear();
    }

    for (int i = 0; i < n; i++)
        b[a[i]/c].push_back(a[i]);
    
    k = 0;
    for (int i = 0; i < c; i++)
        for (size_t j = 0; j < b[i].size(); j++)
            a[k++] = b[i][j];
}

이 접근 방식은 임의의 키 타입과 키 크기로 일반화할 수 있습니다.