[알고리즘] 기수정렬(Radix Sort)이란?

기수정렬이란

• 데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬하는 방식
• 데이터의 각 자릿수끼리 비교하면서 정렬을 수행한다.
• 가장 작은 자릿수부터 비교하는 방법인 LSD(Least-Significant-Digit)와 가장 큰 자릿수부터 비교하는 방법인 MSD(Most-Significant-Digit)가 있다.

---

 

기수정렬 알고리즘 과정

(8,2,7,3,5) 의 기수정렬

한자리수 일땐 데이터의 값이 인덱스가 되어 배열에 정렬된다.

---

만약 2자리 일땐? (28,93,39,81,62,72,38,26)

낮은 자리수로 먼저 분류한 다음, 순서대로 읽어서 다시 높은 자리수로 분류한다.

---

1. 버켓은 큐로 구현
2. 버켓의 개수는 키의 표현 방법과 밀접한 관계가 있다.(이진법2개, 알파벳26개, 십진법10개)
3. 자리수에 따라 큐에 순차적으로 데이터를 삽입한다.
4. 버켓에서부터 순차적으로 dequeue하여 하나의 리스트로 합친다.
5. 버켓 수만큼 반복

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

#define BUCKETS 10
#define DIGITS 4
#define  SIZE 10

//큐코드생략

void radix_sort(int list[], int n)
{
    int i, b, d, factor=1;
    QueueType queues[BUCKETS];

    for(b=0;b<BUCKETS;b++) init(&queues[b]);	// 큐들의 초기화

    for(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;				// 그 다음 자리수로 간다.
    }
}


int main(void)
{
    int list[SIZE];
    srand(time(NULL));
    for (int i = 0; i<SIZE; i++)      	// 난수 생성 및 출력 
        list[i] = rand() % 100;

    radix_sort(list, SIZE); // 기수정렬 호출 
    for (int i = 0; i<SIZE; i++)
        printf("%d ", list[i]);
    printf("\n");
    return 0;
}

---

 

기수정렬 시간복잡도

• n개의 레코드, d개의 자릿수로 이루어진 키를 기수 정렬할 경우, O(dn)의 시간복잡도를 가진다.
• 하지만 실수, 한글, 한자로 이루어진 키는 정렬하지 못한다는 단점이 있다.

---