[알고리즘] 기수 정렬(radix sort)

각각의 자릿수 별로 정렬하여 완벽히 정렬된 배열을 만들어내는 알고리즘

#define N 10
#define K 40
#define D 2

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

int main(void)
{
    radixSort();
}

void radixSort(void)
{
    int i, j;
    for (i = 0; i < D; i++) // 작은 자리수부터 계산하는 이뉴는 stable sort를 위해
    {
        countingSort(i);
        for (j = 0; j < N; j++)
            data[j] = ans[j];
    }
}

void countingSort(int digit)
{
    int i;
    int t1 = (int)pow(10.0, digit); // 10^digit
    int t2 = t1 * 10;               // 10^(digit+1)

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

    for (i = 0; i < N; i++)
    {
        cnt[data[i] % t2]++;
    }

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

    for (i = N - 1; i >= 0; i--)
    {
        ans[--cnt[data[i] % t2]] = data[i];
    }
}

• 시간복잡도 : O(D(N+K))
• 공간복잡도 : O(N+K)