기수 정렬(Radix Sort)



기수정렬?

기수정렬은 자리수별로 비교하여 정렬하는 방법입니다.


비교연산은 하지않고, 정수와 같은 자료의 정렬 속도가 매우 빠릅니다.


복잡도

가장 큰 숫자의 자리수가 d라고할 때 복잡도는 아래와 같습니다.




아래와 같은 배열이 있을 때 


가장 큰 숫자의 자리수는 3이므로 정렬을 3번 진행합니다.


각 자리수에 해당하는 큐에 순서대로 데이터를 삽입합니다.


가장먼저 1의자리 정렬입니다.



1의자리를 기준으로 정렬된 데이터를 

10의자리 기준으로 정렬합니다.



마지막으로 10의자리 기준으로 정렬된 데이터를

100의자리 기준으로 정렬합니다.


정렬한 데이터를 큐에서 전부 꺼내주면 정렬이 완료됩니다.


큐를 이용한 기수 정렬 예제


많은 예제들을 찾아봤는데, 0~9 총 10개의 큐를 만들어서 진행하는 예제가 많았습니다.


굳이 10개의 큐가 필요할까? 라는 생각을 하게 되었고, 큐 하나만 이용해서 정렬을 진행해 봤습니다.



Queue put(),get()함수 


Queue관련 내용은 생략하겠습니다.


Queue관련 내용은 아래 포스팅 참고바랍니다.


[Data Strcuture] 큐(Queue)



#include <stdio.h>
#define MAX 20
// QUEUE

int queue[MAX];
int front, rear = 0;

int put(int k){
if((rear+1) % MAX == front){
printf("QUEUE OVER FLOW!\n\n");
return -1;
}else{
queue[rear] = k;
rear = ++rear % MAX;
return 1;
}
}

int get(){
int k;
if(front == rear){
printf("QUEUE UNDER FLOW!\n\n");
return -1;
}else{
k = queue[front];
front = ++front % MAX;
return k;
}
}

// ARRAY
void print_array(int array[], int size){
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n");
}


기수정렬 함수


가장 큰 숫자를 찾아서 자리수를 구한 뒤


0~9까지 각 자리에 맞는 숫자가 나올때 큐에 삽입하고


반복이 끝나면 큐에서 배열에 담고 큐를 초기화 하는 방법으로 진행 했습니다.


void radix_sort(int array[], int size){
int max = array[0];
int digit = 0;
int factor = 1;
for(int i=1; i<size; i++){
if(max<array[i]) max = array[i];
}
for(int i=max; i>0;i/=10){
digit++;
}

for(int i =0; i<digit; i++){
for(int j=0; j<10; j++){ // 0~9
for(int k=0; k<size; k++){
if((array[k]/factor)%10==j){
put(array[k]);
}
}
}
factor *=10;
for(int i=front; i!=rear; i++){
array[i] =get();
}
printf("########### %d ROUND ###########\n",i+1);
print_array(array,size);
front=rear=0;
}
}


배열 출력 함수


void print_array(int array[], int size){
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n");
}


실행 함수


void main(){
int array[] = {11,1,83,202,55,4,119,81,15,47,19,28};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
radix_sort(array, size);
}


실행 결과



참고 : 위키백과(기수 정렬)



관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)



저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 합병 정렬(Merge Sort)  (0) 2019.05.04
[C] 힙 정렬(Heap Sort)  (0) 2019.05.01
[C] 퀵 정렬(Quick Sort)  (0) 2019.04.24
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20

+ Recent posts

티스토리툴바