Radix Sort

https://m.blog.naver.com/PostView.nhn?blogId=itperson&logNo=220847283030&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

기수 정렬

  • 원소들이 있을 때 각각의 자리수 별로 정렬을 하여 완벽히 정렬된 배열을 만들어 내는 알고리즘
  • 일의 자리부터 정렬하면서 최고 자리 수 까지 정렬 해 간다
  • 가령 56 , 59가 있으면 1의 자리에서 6이 작으니까 앞에 오고, 10의자리 비교 시 5로 값이 같더라도, stable sort가 보장되기 때문에 순서가 바뀌지 않고 그대로 56, 59 순서가 유지 된다. 이런식으로 최고 자리수 까지 정렬해가면 stable sort라는 속성 덕분에 전체적으로 정렬이 됨
  • 카운팅 소트가 O(n+k)인데 자리수 d만큼 카운팅 소트를 하므로, 시간 복잡도는 O(d (n+k))
  • 정렬 자체는 카운팅 소트(stable sort)로 하면 됨
#include <iostream>
using namespace std;
#define N 10
#define K 40
#define D 2 //자리 수 

int data[N] = { 40, 6, 1, 9, 3, 15, 15, 3, 6, 6 };
int cnt[K + 2];
int ans[N];

void countingSort(int digit){

    int t1 = (int)pow(10.0, digit);
    int t2 = t1 * 10;

    for (int i = 0; i <= K; ++i)
        cnt[i] = 0;

    for (int i = 0; i < N; ++i)
        cnt[(data[i] % t2) / t1] ++;

    for (int i = 1; i <= K; ++i)
        cnt[i] += cnt[i - 1];

    for (int i = N - 1; i >= 0; --i)
        ans[--cnt[(data[i] % t2) / t1]] = data[i];

}

void radixSort(void){
    for (int i = 0; i < D; ++i){
        countingSort(i);
        for (int j = 0; j < N; ++j)
            data[j] = ans[j];
    }
}

int main(){
    radixSort();
    for (int i = 0; i < N; ++i)
        cout << data[i] << endl;
    return 0;
}
  • t1, t2는 각 자리수를 구하여 counting sort 하기 위해

You may also like...