C Data Structure - 기수 정렬

기수 정렬이다. 드디어 정리할 시간이 다가왔다.

Q. 기수 정렬에서 기수란 무엇인가?

A. 숫자 표현(진법체계)에 기준이 되는 수를 뜻한다. 예를 들자면 16진, 10진, 8진, 2진 등을 기수라고 한다.

Q. 그럼 기수 정렬은 무엇인가? 기수를 통해서 어떻게 정렬을 이뤄내는가?

A. 예제를 통해서 보겠다.

정렬이 되는 대상들을 하나의 진법 속 요소들로 가정하고,

해당 진법 배열에 값을 모두 넣은 후, 단순히 순서대로 꺼내기만 한다.

이런 식으로 동일한 기수의 요소들끼리 해당 기수의 버킷을 이용하여 정렬이 이루어지는 것이 기수 정렬이다.

알파벳을 정렬할 때

여러 자리도 정렬이 가능하다.

중요한 것은 해당 기수의 버킷에 넣고 다시 버킷의 처음부터 순서대로 꺼낼 뿐이다. 그러니까 값의 비교가 이루어지지 않는다는 것이다! 그렇기 때문에 정렬할 대상들에 따라 반복문을 여러 번 사용해야할 수도 있고, 중간에 갑자기 진행을 끊을 수도 있으며, 정렬할 수 있는 대상이 제한이 되기도 한다.

예를 들어, 1, -5, 100 이런 요소들에 대해서는 정렬이 불가능하다. - 를 기수 버킷으로 어떻게 표현할 것이란 말인가?

다음으로 간단한 숫자 정렬하는 예제를 보겠다.

코드 및 실행 결과

#include <stdio.h>
 
int main(void)
{
    int radix_bucket[10]; // 0 ~ 9 까지 
    int data[] = { 5, 1, 7, 2, 4, 9, 0 };
    int data_len = sizeof(data) / sizeof(int);
 
    int i = 0, j = 0;
 
    // 기수 버킷 초기화
    for (i = 0; i < 10; i++)
        radix_bucket[i] = -1;
 
    // 정렬 되지 않은 데이터 출력
    for (i = 0; i < data_len; i++)
        printf("%d ", data[i]);
    fputc('\n', stdout);
 
    // 기수 버킷 이용
    for (i = 0; i < data_len; i++)
        radix_bucket[data[i]] = data[i];
 
    // 기수 버킷에서 값을 옮김
    for (i = 0, j = 0; i < 10; i++)
        if (radix_bucket[i]!=-1)
            data[j++] = radix_bucket[i];
 
    // 정렬된 데이터 출력
    for (i = 0; i < data_len; i++)
        printf("%d ", data[i]);
    fputc('\n', stdout);
 
    return 0;
}

 정렬 전 / 기수 정렬 후