기수정렬((Radix Sort)

기수 정렬(radix sort)은 counting sort 처럼 비교연산(comparision operation)을 하지 않고 입력된 원소들간의 순서가 보장되는 stable 한 정렬 알고리즘이다. 
(comparision, stable 에 대해서는 여기 참고)
기수 정렬은 정렬 방법의 특수성(counting sort를 사용함) 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용(bucket sort가 부동소수점을 정렬할때 유용하다)할 수 없지만 정수와 같은 자료를 정렬할때 선형시간(lienar time)으로 정렬하기 때문에 시간복잡도가 O(dn)로 매우 빠른 정렬알고리즘이다.

그럼 정수 정렬시 counting sort도 선형시간으로 정렬이 가능한 정렬알고리즘이라고 하였고 radix sort 내부적으로 counting sort를 이용한다고 하였는데 counting sort 가 아닌 radix sort를 사용해야할 때는 언제일까? 카운팅정렬(counting sort)에서 알아본것 처럼 원소의 범위(range)가 너무 큰 경우 빈도수를 저장할 임시 메모리가 많이 필요하고 필요한 연산도 더 증가하게 된다. 
하지만 기수정렬은 최하위자리부터 (LSD : least significant digit) -> 최상위자리(MSD : most significant digit)까지 숫자 0 - 9 범위에 있는 것만 단계적으로 정렬하기 때문에 그럴필요가 없다.
따라서 counting sort는 정수나 데이터 크기가 작은 경우(range가 작은경우)에 사용하면되고 기수정렬은 counting sort로 하면 비효율적인경우 대안으로 사용하면 된다. 


위에서 잠시 언급한 것처럼 기수 정렬의 알고리즘은 매우 간단한데 정수형의 낮은자리수부터 비교하여 높은 자리수까지 정렬(digit sort)해 나간다는 것을 기본 개념으로 하고 있다. 
예를들어 그림1과 같은  자료가 있다면 

 

그림1. radix sort 정렬 과정

[출처] https://www.codingeek.com/algorithms/radix-sort-explanation-pseudocode-and-implementation/

 

 

그럼 젤 처음 1의 자리수를 정렬 -> 10의자리수를 정렬 -> 100의자리수를 정렬하면 최종적으로 정렬된 A를 얻을수 있게 된다. 자리수마다 정렬을 하면 최종적으로 정렬된 A를 얻게 되는 이유는 어찌보면 radix sort 가 stable sort 이기 때문이다. 
구현은 counting sort과 queue를 이용하여 정렬하는 2가지 방법이 있는데 여기서는 counting sort 를 이용해 정렬하도록 한다. 

 

import java.util.Random;
 
public class RadixSort {
 
    // Main function to test performance sorting 1 million integers.
    // Results in about 220 ms on a 2.3 Ghz Core i5 processor w/4GB 1333 Mhz RAM
    public static void main(String[] args){
        final int SIZE = 1000000;
 
        Random r = new Random();
        int[] test = new int[SIZE];
 
        for (int i = 0; i < SIZE; i++){
            test[i] = r.nextInt(Integer.MAX_VALUE);
        }
 
        long start = System.currentTimeMillis();
        test = sort(test);
        long end = System.currentTimeMillis();
 
        for (Integer i : test){
            System.out.println(i);
        }
 
        System.out.println(end-start);
    }
 
    // Sort the numbers beginning with least-significant digit
    public static int[] sort(int[] input){
 
        // Largest place for a 32-bit int is the 1 billion's place
        for(int place=1; place <= 1000000000; place *= 10){
            // Use counting sort at each digit's place
            input = countingSort(input, place);
        }
 
        return input;
    }
 
    private static int[] countingSort(int[] input, int place){
        int[] out = new int[input.length];
 
        int[] count = new int[10];
 
        for(int i=0; i < input.length; i++){
            int digit = getDigit(input[i], place);
            count[digit] += 1;
        }
 
        for(int i=1; i < count.length; i++){
            count[i] += count[i-1];
        }
 
        for(int i = input.length-1; i >= 0; i--){
            int digit = getDigit(input[i], place);
 
            out[count[digit]-1] = input[i];
            count[digit]--;
        }
 
        return out;
 
    }
 
    private static int getDigit(int value, int digitPlace){
        return ((value/digitPlace ) % 10);
    }
 
}

[코드출처] https://gist.github.com/yeison/5606963