기수 정렬 (Radix Sort)

1. 개념 설명

(1) 기수 정렬은 간단하게 말하면 데이터의 N진법을 기준으로 정렬하는 알고리즘이다.

( 예를 들면, N이 10이고 정렬할 데이터는 10, 5, 15, 234, 1이라고 하자. 그렇다면 아래와 같이 기준을 잡는다. )

 

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

 

( 이 과정을 거치면 정렬된 결과인 1, 5, 10, 15, 234가 나오게 된다. )

 

(2) 기수 정렬은 계수 정렬의 비효율성을 개선하기 위해서 사용할 수 있다.

 

 

 

2. 과정

by wiki

- 실제로 수행되는 과정이며, 기수 정렬 알고리즘 중 *LSD를 시각화한 것이다.

( 기수 정렬의 방식으로 LSD와 MSD가 있다. )

( LSD는 Least Significant Digit의 약자로 가장 작은 자릿수부터 정렬을 진행해 나가는 방식을 말한다. )

( MSD는 Most Significant Digit의 약자로 가장 큰 자릿수부터 정렬을 진행해 나가는 방식을 말한다. )

( EX) a와 ab 사전순으로 정렬할 때 )

 

 

 

3. 코드

public class RadixSort {
    private static int[] A = { 38, 27, 43, 9, 3, 82, 10 };
    private static final int BUCKET_SIZE=10; //자릿수는 0~9까지가 최대이므로, bucket 사이즈는 10
    
    public static void main(String[] args) {
        System.out.println("정렬 전: " + Arrays.toString(A));
        radixSort(A.length);
        System.out.println("정렬 후: " + Arrays.toString(A));
    }
    
    public static void radixSort(int len) {
        Queue<Integer>[] bucket = new LinkedList[BUCKET_SIZE];
        for(int i=0; i<BUCKET_SIZE; i++) {
            bucket[i] = new LinkedList<>();
        }
        
        // 정렬할 자릿수의 크기 만큼 반복한다.
        // 현재 배열의 가장 큰 수는 10의 자리이므로, 2번 반복하게 한다.
        int m = 1;
        for(int d=0; d<2; d++) {
            for(int i=0; i<len; i++) {
                bucket[(A[i]/m)%10].add(A[i]);
            }
            
            for(int i=0, j=0; i<BUCKET_SIZE; i++) {
                while(!bucket[i].isEmpty()) {
                    A[j++] = bucket[i].poll();
                }
            }
            m *= 10;
        }
    }
}

 

 

 

 

4. 시간 복잡도

(1) 기수 정렬의 시간복잡도는 O(D*(N+B))이다. 

( D: 길이가 가장 긴 자릿수 )

( B: 자릿수는 0~9까지이므로 고정 값 10 ) -> 코드에서는 BUCKET_SIZE

( N: 입력 데이터의 수 )

 

 

 

5. 공간 복잡도

(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(n)이다.

 

 

 

6. 장점

(1) 대부분의 알고리즘들은 모두 데이터끼리의 직접적인 비교를 이용하는데, 그럴 경우 시간 복잡도는

O(NlogN)보다 작아질 수 없다. 그러나, 이 기수 정렬은 자릿수가 있는 데이터(정수, 문자열)를 직접적인 비교

없이 정렬을 수행하기 때문에, 시간복잡도가 O(N)으로 퀵 정렬보다 빠른 시간복잡도가 나오는 것이 가능하다.

 

(2) 가장 큰 장점은 반드시 끝까지 가지 않아도 중간에 정렬이 완료될 수 있다는 것이다.

( 단, 중간에 데이터를 점검해야 하므로 코드를 추가해야 한다. -> 구현이 복잡해진다. )

 

 

 

7. 단점

(1) 기수 정렬은 자릿수가 적 4바이트 정수 등에서나 제대로된 성능이 발휘되고 자릿수가 무제한에 가까운

문자열 정렬 등에 사용할 경우 오히려 퀵 정렬보다 느릴 수 있다.

 

(2) 만약 부동 소수점의 경우는 부호 여부, 지수부, 기수부에 대해 각각 기수정렬을 실행해야 하므로 까다로울 수 있다.

 

(3) 중간 결과를 저장할 BUCKET 공간이 필요하다.