12. 기수 정렬 (A.K.A Radix sort)

출처: https://tinyurl.com/y287lhew

---

기수 정렬

출처: https://youtu.be/LyRWppObda4

기수 정렬 알고리즘 중 LSD를 시각화한 것.

시간 복잡도는 (k는 데이터의 자릿수를 의미한다.)

데이터끼리 직접적인 비교를 하여 정렬하는 알고리즘의 경우 시간복잡도는보다 작아질 수 없다.

기수 정렬은 자릿수가 있는 데이터(정수, 문자열 등)에서만 수행이 가능하며, 데이터끼리의 직접적인 비교 없이 

정렬을 수행한다.

비교를 이용한 정렬이 아니기 때문에 k가 상수일 경우 시간복잡도가으로, 퀵정렬보다 빠른 시간복잡도가 나오는 것이 가능하다.

다만 이 알고리즘은 자릿수가 적은 4바이트 정수 등에서나 제대로 된 성능을 발휘할 수 있으며, 자릿수가 무제한에 가까운 문자열 정렬 등에 사용할 경우 오히려 퀵정렬보다 느릴 수 있고, 부동 소수점의 경우는 부호여부, 지수부, 가수부에 대해 각각 기수정렬을 실행해야 한다.

기수 정렬의 방식은 데이터가 x진법이라고 가정하자.

0번부터 x-1번까지의 리스트를 만들어 놓고, 각 데이터를 순서대로 현재 자릿수의 숫자가 가리키는 리스트에 밀어넣고, 리스트를 0번부터 x-1번까지 순서대로 이어붙인다.

이 과정을 가장 낮은 자릿수부터 가장 높은 자릿수까지 반복하면 정렬이 끝나게 된다.

예시

10, 5, 15, 234, 1: 10진법, 최대 3자리 수인 정수들을 정렬해보자. (편의상 010, 005, 015, 234, 001로 표기.)

100의 자리: 0) 010, 1) 001, 4) 234, 5) 005, 015. 순서대로 이어붙이면 010, 001, 234, 005, 015.

101의 자리: 0) 001, 005, 1) 010, 015, 3) 234. 순서대로 이어붙이면 001, 005, 010, 015, 234.

102의 자리: 0) 001, 005, 010, 015, 2) 234. 순서대로 이어붙이면 001, 005, 010, 015, 234.

마지막 자리까지 과정을 거치면 정렬된 결과인 1, 5, 10, 15, 234가 나온다.

실제 프로그램에서 정수를 정렬하는 코드를 짜는 경우, 10진법 대신 컴퓨터가 바이트 단위로 처리하기 쉬운 2진법을 사용하고, 각 자릿수를 정렬하는 과정은 밑의 카운팅 정렬을 이용하는 경우가 많다.

그래서 코드를 짜면 퀵 정렬보다도 훨씬 빠른 속도로 정수를 정렬할 수 있다.

다만 위에 설명된 대로 이는 자릿수가 적은 상황에서만 그렇고 대부분의 경우에는 그렇지 않다.

그 이유는 시간 복잡도가 엄밀하게는<이 아니라 이기 때문이다.

해당 데이터의 자릿수(k)는 상수로 간주하지만 어쨌든 k는 log에 해당되므로, 데이터의 수(n)가 데이터의 최댓값보다 더 큰 경우가 아니면 k(자릿수)가보다 크기 때문이다.

 

특징요약.

 

1. 시간 복잡도는

 

2. 자리수가 고정되어 있어서 안정성이 있는 정렬 방식

---

Radix sort 예제 C 코드

#include <stdio.h>
#include <string.h>
void radix_sort(int a[], int size, int base) {
    int ex, i, j, max = a[0];
    for(i=1; i<size; i++) if(a[i]>max) max=a[i];
    for(ex=1; ex<=max; ex*=base) {
    	int output[size], count[base];
    	memset(count,0,sizeof(count));
    	for(i=0; i<size; i++) count[(a[i]/ex)%base]++;
    	for(i=1; i<base; i++) count[i] += count[i-1];
    	for(i=size-1; i>-1; i—) {
    		j = (a[i]/ex)%base;
    		output[count[j]-1] = a[i];
    		count[j]—;
    	}
    	for(i=0; i<size; i++) a[i] = output[i];
    }
}
int main() {
    int arr[] = {9,1,22,4,0,1,22,100,10};
    int size = sizeof(arr)/sizeof(int);
    radix_sort(arr, size, 10);
    for(int i=0; i<size; i++) printf("%d ", arr[i]);
    // 0 1 1 4 9 10 22 22 100 
}

결과.

결과.

---

Radix sort 예제 C 코드 2

#include <iostream>
#include <queue>
 
int main(void)
{
    int arr[8] = { 170, 45, 75, 90, 2, 24, 802, 66 };
    std::queue<int> radix[10]; // 자리수에 대한 큐 배열
 
    int max = arr[0];
    int d = 1; // 최대자리수
 
    // 최대 자리수를 구하기 위해서 최댓값을 찾아낸다.
    for (int i = 1; i < 8; i++)
        if (max < arr[i]) max = arr[i];
 
    // 최대 자리수를 구해낸다.
    while (max/10){
        d *= 10;
        max /= 10;
    }
 
    int mod = 10;
    int dMin = 1;
 
    while (dMin<=d){
        // 자리수에 따라 큐에 집어넣는다.
        for (int i = 0; i < 8; i++){
            radix[(arr[i] % mod)/dMin].push(arr[i]);
        }
 
        // 큐에 들어간 값들을 자리수 크기 순으로 다시 배열에 집어넣는다.
        for (int i = 0, j = 0; i < 10;){
            if (radix[i].size()){
                arr[j++] = radix[i].front();
                radix[i].pop();
            }
            else i++;
        }
 
        dMin *= 10;
        mod *= 10;
    }
 
    for (int i = 0; i < 8; i++) std::cout << arr[i] << ' ';
 
    return 0;
}
//https://sexycoder.tistory.com/74