자료구조 :: 정렬(4) 큐를 이용한 기수 정렬

# 기수 정렬(radix sort)

RadixSort.cpp

기수 정렬은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 기법
이다. 기수정렬은 O(kn)의 시간 복잡도를 가지는데 대부분 k<4이하이다. 다만 기수정렬이 추가적인 메모리를
필요로 한다는 것인데 이를 감안하더라도 기수 정렬이 다른 정렬 기법보다 빠르기 때문에 상당히 인기 있는 정렬
기법 중 하나이다. 단점은 정렬할 수 있는 레코드의 타입이 한정된다는 점이다. 즉 기수정렬을 사용하려면 레코드
키들이 동일한 길이를 가지는 숫자나 문자열로 구성되어 있어야 한다.

기수정렬의 원리는 10개의 버킷(bucket)을 만들어서 입력 데이터를 각 자리수의 값에 따라 상자에 넣는다.
그리고 각 왼쪽 상자부터 순차적으로 버킷안에 들어 있는 숫자를 읽으면 정렬된 숫자를 얻을 수 있다.
10진법의 수의 경우 10개 버킷을 이용할 수 있다.

예를 들어 9 3 1 4 이란 숫자를 차례로 버킷에 넣으면

BUCKET 0
BUCKET 1  1
BUCKET 2
BUCKET 3  3
BUCKET 4  4
BUCKET 5
BUCKET 6
BUCKET 7
BUCKET 8
BUCKET 9  9

그리고 다시 순차적으로 버킷을 읽어 들이면 1 3 4 9 와 같이 정렬된 값을 얻을 수 있다..(이야..)
이 버킷은 먼저 들어간 값이 먼저 나오므로 큐로 구현할 수 있다.

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define random(n) (rand()%n) 
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t)) 

typedefstruct QueueNode { 
int item; 
    QueueNode *link; 
}QueueNode; 

typedefstruct { 
    QueueNode *front, *rear; 
}QueueType; 

void Init(QueueType *q) 
{ 
    q->front=q->rear=NULL; 
} 

int is_empty(QueueType *q) 
{ 
return (q->front==NULL); 
} 

void Enqueue(QueueType *q, int item) 
{ 
    QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode)); 

    temp->item=item; 
    temp->link=NULL; 

if(is_empty(q)) 
    { 
        q->front=temp; 
        q->rear=temp; 
    } 
else
    { 
        q->rear->link=temp; 
        q->rear=temp; 
    } 
} 

int Dequeue(QueueType *q) 
{ 
    QueueNode *temp = q->front; 
int item; 

if(is_empty(q)) 
    { 
        printf("큐가 비어있습니다\n"); 
return -1; 
    } 

    item=temp->item; 
    q->front=q->front->link; 

if(q->front==NULL) 
        q->rear=NULL; 

    free(temp); 

return item; 
} 

void RadixSort(int *list, int n) 
{ 
constint BUCKETS=10; // 10진법
constint DIGITS=2;   // 숫자의 자릿수 
int i,j,k; 
int factor=1; // 증가량 1,10,100,...
    QueueType queue[BUCKETS]; 

for(i=0;i<BUCKETS;i++) 
        Init(&queue[i]); // 큐 초기화

for(k=0;k<DIGITS;k++) 
    { 
for(i=0;i<n;i++) 
            Enqueue(&queue[(list[i]/factor)%10],list[i]); // 자리수에 따라 큐에 삽입

for(i=j=0;i<BUCKETS;i++)  
        { 
while(!is_empty(&queue[i])) // 모든 큐가 NULL 일때 까지
                list[j++]=Dequeue(&queue[i]); // 정렬된 데이터 삽입
        } 
        factor*=10; // 다음 자릿수로 변경
    } 
} 

void ScreenOut(int *pList, int count) 
{ 
int i; 
for(i=0;i<count;i++) 
        printf("%d ",pList[i]); 

    puts(""); 
} 

int main() 
{ 
int i,input; 
int *list; 

    srand((unsignedint)time(NULL)); 

    printf("Input Data Count : "); 
    scanf("%d",&input); 

    list=(int *)malloc(sizeof(int)*input); 

for(i=0;i<input;i++)     
        list[i]=random(100); 

    printf("Insert Data : "); 
    ScreenOut(list,input); 

    RadixSort(list,input); 

    printf("Sorting Data : "); 
    ScreenOut(list,input); 

    free(list); 

return0; 
}