기수 정렬(radix sort)

기수 정렬은 흔히 말하는 n진법으로 나타낸 수에서 각 자릿수별로 비교 없이 수행하는 정렬 알고리즘입니다.

비교를 하는 대신 버킷이라 부르는 배열 이용해서 정렬을 합니다.

시작하는 자리수에 따라서 다음과 같이 분류합니다.

LSD - 낮은 자리수부터 높은 자리수 순서로 진행

MSD - 높은 자리수부터 낮은 자리수 순서로 진행

MSD 정렬은 문자열이나 고정된 길이의 정수 표현의 정렬을 할 때 적합하고, 세분화하거나 재귀를 사용하는 경우에 사용하기 좋습니다.
또한, 가장 큰 자리수부터 시작해서 점진적으로 정렬을 완성해나가기 때문에 끝까지 탐색을 안하고도 정렬이 완료될 수 있다는 장점이 있습니다.
하지만 정렬 과정에서 길이가 짧은 수를 가장 긴 길이의 숫자로 확장하고서 정렬하기 때문에, 구현이 복잡해질 수 있습니다.

둘의 성능적인 차이는 없지만 구현상의 편의성 때문에 LSD에 관한 설명으로 이후 설명을 하겠습니다.

동작하는 방식을 나타내면 다음과 같습니다.

구현

import java.util.Arrays;

public class radixSort {

    public static void main(String[] args) {
        int[] data = new int[]{170, 45, 75, 90, 2, 24, 802, 66};
        data = radixSort(data,3,10);
        System.out.println(Arrays.toString(data));
    }

    /**
     *
     * @param data 정수 배열
     * @param numLen 숫자의 최대 자리수
     * @param radix 기수(10진법인 경우 10)
     */
    public static int[] radixSort(int[] data, int numLen,int radix){
        int[] count = new int[radix];//특정 자리에서 숫자들을 카운트하는 배열
        int[] temp = new int[data.length];//정렬된 배열을 담을 임시 공간(bucket)
        int idx, nowRadix;//idx : index, nowRadix : 현재 확인하는 자리수에 해당하는 숫자
        for(int i = 0;i<numLen;i++){
            for(int j = 0;j<radix;j++){
                count[j] = 0;
            }//자리수별로 정렬하기 때문에 초기화를 진행해야한다.
            System.out.println(Arrays.toString(count));
            nowRadix = (int)Math.pow((double)radix,(double)i);
            for(int j = 0;j<data.length;j++){
                idx = (int)(data[j]/nowRadix)%radix;
                count[idx] = count[idx]+1;
            }//각 숫자가 몇 번 나오는지 count
            for(int j = 1;j<radix;j++){
                count[j] = count[j] + count[j-1];
            }//계수 정렬을 위한 카운트의 누적합을 구한다.
            for(int j = data.length-1;j>=0;j--){
                idx = (int)(data[j]/nowRadix)%radix;
                temp[count[idx]-1] = data[j];
                count[idx] = count[idx]-1;
            }//count 배열을 통해서 각 항목의 위치를 결정
            data = Arrays.copyOf(temp,temp.length);
        }
        return data;

    }

}

시간복잡도

정렬할 숫자의 자리수를 d라고 하면 O(dN)이 됩니다.

장점

문자열, 정수에대한 정렬이 가능하며 퀵소트 등의 O(NlogN) 알고리즘보다 빠르게 동작할 수 있습니다.

단점

부동 소수점은 정렬을 할 수 없습니다.

중간 결과를 저장하는 bucket 공간이 필요합니다.
숫자의 길이가 길어지면 메모리를 많이 사용하기 때문에 사용이 불가능해집니다.