기수 정렬 (Radix Sorting)

앞의 정렬은 모두 레코드들을 비교하여 정렬하였다.

기수정렬은 레코드를 비교하지 않고 정렬하는 방법이다.

입력 데이터에 대해서 어떤 비교 연산도 하지 않고 데이터를 정렬할 수 있다.

정렬에 기초한 방법은 이라는 하한선을 깰 수 없는데 반해 기수 정렬은 이 하한을 깰 수 있는 유일한 정렬방법이다.

기수 정렬은 O(dn)의 시간 복잡도를 가지는데, 대부분 d<10이하 이다.

문제는 기수 정렬이 추가적인 메모리를 필요로 한다는 것인데, 이를 감안하더라도 다른 정렬 기법보다 빠르기에 자주 사용된다.

단점은 정렬할 수 있는 레코드의 타입이 한정된다는 것이다.

즉, 기수 정렬을 사용하려면 레코드의 키들이 동일한 길이를 가지는 숫자나 문자열로 구성되어 있어야 한다.

기수란 숫자의 자릿수이다. 예를 들면 숫자 42는 4와 2의 두 개의 자릿수를 가지고, 이것이 기수가 된다.

자릿수의 값에 따라서 정렬하기 때문에 기수 정렬이다.

기수 정렬은 다단계 정렬이다. 단계의 수는 데이터의 자릿수 개수와 일치한다.

(8, 2, 7, 3, 5)라는 숫자들을 정렬한다고 할 때, 십진수는 각 자릿수가 0~9까지의 값만 있으므로 이것에 착안하여 10개의 버켓(bucket)을 만들어서 입력 데이터를 각 자릿수의 값에 따라 버켓에 넣는다.

그리고 위에서부터 아래로 순차적으로 버켓 안에 들어 있는 숫자들을 읽음으로써 정렬된 숫자 리스트를 얻을 수 있다.

주의할 점은 비교 연산을 전혀 사용하지 않았다. 각 자릿수의 값에 따라 버켓에 넣고 빼는 동작을 되풀이만 했다.

(28, 93, 39, 81, 62, 72, 38, 26)라는 2자릿수를 정렬 할 경우는 다음과 같이 해결한다.

0~99까지 번호가 매겨진 100개의 버켓을 사용하여 앞에서와 마찬가지로 정렬을 할 수 있다.

하지만 더 효과적인 방법은 1의 자릿수와 10의 자릿수를 따로 사용하여 정렬하면, 10개으 버켓만을 사용해도 2자리 정수도 정렬할 수 있다.

먼저 낮은 자릿수로 정렬한 다음, 점점 더 높은 자릿수로 정렬해야 한다.

위 2자릿수 배열의 경우 10의 자릿수를 먼저 사용하고 1의 자릿수를 나중에 사용하면

(81, 62, 72, 93, 26, 28, 38, 39)가 되어 잘못된 결과가 된다.

그러나 1의 자릿수를 먼저 사용하면 같은 버켓을 사용하더라도 (26, 28, 38, 39, 62, 72, 81, 93)이 되어서 정렬하는 것이 가능하다.

각각의 버켓에서 먼저 들어간 숫자들은 먼저 나와야 한다. 따라서 각각의 버켓은 큐로 구현되어야 한다.

큐로 구현되어야 리스트상에 있는 요소들의 상대적인 순서가 유지된다.

버켓에 숫자를 넣는 연산은 큐의 삽입 연산이 되고,

버켓에서 숫자를 읽는 연산은 삭제 연산으로 대치한다.

버켓의 개수는 키의 표현 방법과 밀접한 관계가 있다. 키를 2진법을 사용하여 표현, 정렬한다면 2개만 있으면 된다.

키가 알파벳 문자라면 26개의 버켓이 필요하다.

기수 정렬은 숫자로 이루어진 키의 경우 위와 같이 10개의 버켓으로 분류가 가능하지만 숫자의 이진 표현을 이용해도 기수정렬을 할 수 있다.

예를 들어 32비트의 정수의 경우, 8비트씩 나누어 기수 정렬의 개념을 적용시킬 수 있다. 이 경우 필요한 버켓의 수는 256개이다.

대신 필요한 패스의 수는 4개로 십진수 표현보다 줄어든다.

4자리로 된 정수만을 취급하며, 원형 큐를 사용한다.

/* Queue 관련 소스 ... */
 
#define BUCKETS 10
#define DIGITS 4

void radix_sort(int list[], int n) {
    int b, i;
    for (b = 0; b < BUCKETS; B++)
    init(&queues[b]); // 큐 초기화
    
    for (int d = 0; d < DIGITS; d++) {
        for (i = 0; i < n, i++) // 데이터들을 자릿수에 따라 큐에 입력
            enqueue(&queues[(list[i] / factor) % 10], list[i]);
        
        for (b = i = 0; b < BUCKETS; b++) // 버켓에서 꺼내어 list로 합친다.
            while (!is_empty(&queues[b]))
                list[i++] = dequeue(&queues[b]);
        factor *= 10; // 다음 자릿수로 간다
    }
}

전체 프로그램

#include <stdio.h>
#include <Windows.h>

#define MAX_QUEUE_SIZE 100
#define ARRAY_SIZE 10
#define BUCKETS 10
#define DIGITS 4

typedef struct {
    int queue[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;

void error(char *message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 초기화 함수
void init(QueueType *q) {
    q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType *q) {
    return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType *q) {
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 삽입 함수
void enqueue(QueueType *q, int item) {
    if (is_full(q))
        error("큐가 포화상태입니다.");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}

// 삭제 함수
int dequeue(QueueType *q) {
    if (is_empty(q))
        error("큐가 공백상태입니다.");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

void radix_sort(int list[], int n) {
    int i, factor=1;
    QueueType queues[BUCKETS];
    
    for (int b = 0; b < BUCKETS; b++)
        init(&queues[b]); // 큐 초기화
    
    for (int d = 0; d < DIGITS; d++) {
        for (i = 0; i < n; i++) // 데이터들을 자릿수에 따라 큐에 입력
            enqueue(&queues[(list[i] / factor) % 10], list[i]);
        
        for (int b = i = 0; b < BUCKETS; b++) // 버켓에서 꺼내어 list로 합친다.
            while (!is_empty(&queues[b]))
                list[i++] = dequeue(&queues[b]);
        factor *= 10; // 다음 자릿수로 간다
    }
}

void main() {
    int list[ARRAY_SIZE] = {28, 93, 39, 81, 62, 72, 39, 26, 12, 88};
    
    printf("<기수정렬>\n정렬 이전 배열 : ");
    for (int i = 0; i < ARRAY_SIZE; i++)
        printf("%d ", list[i]);
    printf("\n");
    
    radix_sort(list, ARRAY_SIZE); // 기수 정렬 호출
    
    printf("최종 정렬 결과 : ");
    for (int i = 0; i < ARRAY_SIZE; i++) // 정렬 결과 출력
        printf("%d ", list[i]);
    printf("\n");
    
    system("pause");
}

 

만약 입력 리스트가 n개의 정수를 가지고 있다면 알고리즘의 내부 루프는 n번 반복될 것이다.

만약 각 정수가 d개의 자리수를 가지고 있다고 하면 외부 루프는 d번 반복된다.

따라서 기수 정렬은 O(dn)의 시간 복잡도를 가진다. 시간 복잡도가 d에 비례하기 때문에 기수 정렬의 수행 시간은 정수의 크기와 관련이 있다. 

그러나 일반적으로 컴퓨터 안에서는 정수의 크기가 제한된다. 32비트 컴퓨터의 경우 대개 10개 정도의 자릿수만을 가지게 된다.

따라서 일반적으로는 d는 n에 비하여 아주 작은 수가 되므로 기수 정렬은 O(n)이라고 하여도 무리가 없다.

따라서 기수 정렬은 다른 정렬방법에 비하여 비교적 빠른 수행 시간 안에 정렬을 마칠 수 있다.

그러나 문제점은, 기수 정렬은 정렬에 사용되는 키 값이 숫자로 표현되어야만이 적용할 수 있다는 것이다.

실수, 한글, 한자 등으로 이루어진 키 값을 기수 정렬하고자 할 경우 매우 많은 버켓이 필요하게 되므로 기수 정렬의 적용이 불가능하다.

다른 정렬 방법들은 모든 종류의 키 형태에 적용될 수 있다.