기수 정렬 프로그램

기수 정렬

다른 정렬방법들은 모두 레코드들을 비교하여 정렬한다. 기수 정렬(radix sort)은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 기법이다. 다른 방법들이 이라는 정렬의 이론적인 하한선을 깰 수 없는데비해 기수 정렬은 이 하한선을 깰 수 있는 유일한 기법이다. 사실 기수 정렬은 의 시간 복잡도를 가지는데 대부분 k<4 이하이다. 기수 정렬은 추가적인 메모리를 필요로 하는데, 이런 단점을 감안하더라도 다른 방법들 보다 빠르기 때문에 상당히 인기있는 정렬 기법 중의 하나이다.

기수(radix)란 숫자의 자릿수이다. 예를 들면 숫자 42는 4 와 2 의 두 개의 자릿수를 가지고 이것이 기수가 된다. 기수 정렬은 이러한 자릿수의 값에 따라서 정렬하기 때문에 기수 정렬이라는 이름을 얻었다. 기수 정렬은 다단계 정렬이다. 단계의 수는 데이터의 자릿수의 개수와 일치한다.

| 기수 정렬의 알고리즘

---

RadixSort(A, n)

for  d <- LSD의 위치 to MSD의 위치 do

d번째 자릿수에 따라 0번부터 9번 버킷에 집어넣는다.

버킷에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다.

d++;

---

각각의 버킷에서 먼저 들어간 숫자들은 먼저 나와야 한다. 따라서 각각의 버킷은 큐로 구현되어야 한다. 큐로 구현되어야 리스트 상에 있는 요소들의 상대적인 순서가 유지된다. 버킷에 숫자를 집어넣는 연산은 큐의 삽입 연산이 되고 버킷에서 숫자를 읽는 연산은 삭제연산으로 대치하면 된다. 

• 기수 정렬의 분석

만약 입력 리스트가 n개의 정수를 가지고 있다고 하면 알고리즘의 내부 루프는 n번 반복될 것이다. 만약 정수가 d개의 자릿수를 가지고 있다고 하면 외부 루프틑 d번 반복된다. 따라서 기수 정렬은 의 시간 복잡도를 가진다. 시간 복잡도가 d에 비례하기 때문에 기수 정려의 수행 시간은 정수의 크기와 관련이 있다. 그러나 일반적으로 컴퓨터 안에서의 정수의 크기는 제한된다. 32비트 컴퓨터의 경우에는 대개 10개 정도의 자릿수 만을 가지게 된다. 따라서 일반적으로 d는 n에 비하여 아주 작은 수가 되므로 기수 정렬은 이라고 하여도 무리가 없다.

따라서 기수 정렬은 다른 정렬 방법에 비하여 빠른 수행 시간에 정렬을 마칠 수 있다. 그러나 문제점은 정렬에 사용되는 키값이 자연수로 표현되어야만 적용이 가능하다는 것이다. 만약 예를 들어 실수나 한글, 한자 등으로 이루어진 키값을 이 방법으로 정렬하고자 할 경우 매우 많은 버킷이 필요하게 되므로 적용이 불가능하다. 다른 정렬 방법들은 모든 종류의 키 형태에 적용될 수 있음을 기억하라.

---

#include "CircularQueue.h"

#define MAX_SIZE 1024

#define BUCKETS 10

#define DIGITS 4

// 기수 정렬 프로그램

void radixSort(int list[], int n) {

CircularQueue queues[BUCKETS];

int factor = 1;

for (int d = 0; d < DIGITS; d++) {

for (int i = 0; i < n; i++) // 데이터들은 자릿수에 따라 큐에 삽입

queues[(list[i] / factor) % 10].enqueue(list[i]);

int i;

for (int b = i =0; b < BUCKETS; b++) // 버킷에서 꺼내어 list로 합친다.

while (!queues[b].isEmpty())

list[i++] = queues[b].dequeue();

factor *= 10; // 그 다음 자릿수로 간다.

printArray(list, n, "RadixSort");

}

}