기수 정렬을 왜 쓰는가? 기수 정렬은 제한적으로 사용이 가능하지만 퀵 정렬보다 더 빠르다. 퀵 정렬의 시간복잡도가 \(O(n\log _2n)\) 인데, 기수 정렬의 시간복잡도는 \(O(dn)\)이다. 여기서 \(d\) 는 가장 큰 데이터의 자릿수이다. 왜 시간복잡도가 \(O(dn)\)인지는 아래의 설명과 그림을 보면 알 수 있다.
기수 정렬에는 기준으로 삼는 자리수를 MSD와 LSD 방식이 있다. MSD(Most Significant Digit) 방식은 가장 큰 자릿수부터 비교하는 것이고, LSD(Least Significant Digit) 방식은 가장 작은 자릿수부터 비교하는 것이다. 말로만 들으면 어떻게 하는지 감이 잘 안 잡히니까 그림을 보자. 아래 그림은 작은 자리 수부터 배열하는 LSD 방식이다.
이미지 출처 : http://itqomcom.blogspot.com/2016/05/1_19.html
여기서 비교는 가장 큰 숫자의 자릿수 d만큼(3자리 수 234가 있다고 하더라도 0234로 생각하면 된다) 비교하는데, 각각의 비교 for문 안에는 각 데이터 수 n만큼을 살펴봐야 한다. 따라서 기수 정렬의 시간복잡도는 \(O(dn)\)이 된다.
기수 정렬은 각 데이터를 큐로 구현한 버킷들에 집어넣었다가 순서대로 빼는 것으로 생각할 수 있다. 왜 큐냐면, 우선순위가 먼저인 것이 먼저 들어가서 먼저 나와야 하기 때문이다. FIFO(First In First Out) 방식의 자료구조인 큐가 적합하다.
아래는 큐를 이용한 기수 정렬의 소스코드이다. 큐 소스코드는 다른 게시물에 있다. 큐 코드와 아래 소스코드 모두 윤성우 책에 있는 내용을 가져왔다.
기수 정렬 소스코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Queue.h"
#define BUCKET_NUM 10
void RadixSort(int arr[], int num, int maxLen){
Queue buckets[BUCKET_NUM];
int bi, pos, di, divfac = 1, radix;
//버킷 초기화
for(bi=0; bi<BUCKET_NUM; bi++){
QueueInit(&buckets[bi]);
}
//가장 긴 길이의 데이터만큼
for(pos=0; pos<maxLen; pos++){
//정렬대상의 수만큼
for(di=0; di<num; di++){
//divfac번쨰 자리의 숫자 추출
radix = (arr[di] / divfac) % 10;
//추출한 숫자 기준으로 버킷에 데이터 저장
Enqueue(&buckets[radix], arr[di]);
}
//버킷 수만큼 반복
for(bi=0, di=0; bi<BUCKET_NUM; bi++){
while(!QIsEmpty(&buckets[bi])){
arr[di++] = Dequeue(&buckets[bi]);
}
}
divfac *= 10;
}
}
int main(void){
int arr[20];
int i;
int len = sizeof(arr)/sizeof(int);
srand(time(NULL));
for(i=0; i<20; i++){
arr[i] = rand()%10000 + 1;
}
RadixSort(arr, len, 5);
for(i=0; i<len; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
| cs |
참고
윤성우.(2012).열혈 자료구조.오렌지미디어
댓글 없음:
댓글 쓰기