[정렬] 기수 정렬

기수 정렬이란?

낮은 자리수부터 비교하여 정렬해가는 알고리즘이며 비교 연산이 불필요한 정렬이다. 
자릿수에 해당되는 값에 따라 버킷에 데이터들을 삽입하기 때문에 비교 연산이 불필요하지만 자릿수만큼의 추가적인 메모리 공간이 필요하다.  (또한 자릿수만큼의 추가적인 로직도 필요하다)

자릿수가 비정상적으로 큰 데이터가 존재한다면 쓸데없는 메모리의 크기를 차지하게 된다.

 

구현과 시간 복잡도 

자바를 이용한 구현

    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();

        for(int i=0; i<10; i++) {
            buckets.add(new LinkedList<>());
        }

        // 1
        int digit = radixSort.getMaximumDigit();
        // 2
        for(int i=1; i<=digit; i++) {
            // 2-1
            for (int number : numbers) {
                // 2-1-1
                int digitValue = radixSort.getDigitValue(number, i);
                // 2-1-2
                buckets.get(digitValue).offer(number);
            }

			/ 2-2
            int idx = 0;
            for (LinkedList<Integer> bucket : buckets) {
                while (!bucket.isEmpty()) {
                    numbers[idx++] = bucket.poll();
                }
            }
        }

        System.out.println(Arrays.toString(numbers));

    }

    private int getMaximumDigit() {
        int max = 0;
        for (int number : numbers) {
            max = Math.max((int) Math.log10(number)+1, max);
        }
        return max;
    }

    private int getDigitValue(int number, int digit) {
        return (int) (number / Math.pow(10, digit-1)) % 10;
    }

1. 자릿수를 구한다. (digit) 

2. 1의 자리부터 digit 자리까지 반복한다. O(d)

  2-1. 모든 데이터에 대해서 반복한다. O(n)

    2-1-1. 자릿수에 해당되는 데이터를 뽑아낸다.

    2-1-2. 뽑아낸 데이터를 이용하여 해당되는 Bucket에 데이터를 삽입한다. 

  2-2. bucket에 들어간 순서대로 데이터를 정렬한다.  

 

시간 복잡도

모든 자릿수에 대해 반복하기 때문에 O(자릿수) 

그리고 자릿수마다 모든 데이터에 대해 정렬을 수행하기 때문에 O(데이터 수) 

따라서 기수 정렬의 시간 복잡도는 O(자릿수 * 데이터 수)

즉, O(dn) (d는 최대 자릿수) 이다.