[Algorithm] 기수 정렬(Radix Sort)

기수 정렬(Radix Sort)

출처

기수 정렬(Radix Sort)은 데이터를 구성하는 기본 요소, 즉 기수를 이용해서 정렬을 진행하는 알고리즘입니다.
기수 정렬은 비교 정렬 알고리즘과는 다르게 비교 없이 수행하는 정렬 알고리즘으로 입력 데이터를 여러 개의 버킷으로 나누고 각 버킷에 속한 데이터들을 개별적으로 정렬하는 버킷 정렬 정렬의 일종으로 취급되기도 합니다.

데이터의 각 자릿수를 기준으로 정렬을 수행하기 때문에 자릿수가 존재하지 않는 데이터를 기수 정렬로 정렬하는 것은 불가능합니다.
또한 기수 정렬은 정렬 방법의 특수성 때문에 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없고 길이가 다른 데이터들을 대상으로는 정렬이 불가능합니다.

예제

먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다.

[121, 432, 564, 23, 1, 45, 788]

위 배열을 오름차순으로 정렬하기 위한 기수 정렬 알고리즘은 다음과 같이 동작합니다.

먼저 요소 중 가장 큰 값을 찾습니다. 해당 배열의 가장 큰 값은 788이므로 788의 자릿수인 백의 자리만큼 즉 3번의 루프를 돌게됩니다.
그후 일의 자릿수를 기준으로 해당 배열의 요소를 정렬합니다.

다음 십의 자릿수를 기준으로 요소들을 정렬합니다.

마지막으로 백의 자릿수를 기준으로 요소들을 정렬합니다.

출처

시간 복잡도

기수 정렬의 시간 복잡도는 주로 데이터의 자릿수에 의해 영향을 받습니다. 기수 정렬은 각 자릿수에 대해 정렬을 수행하므로 최악의 경우에도 모든 자릿수에 대해 정렬을 수행하게 됩니다.
데이터의 최대 자릿수를 d라고 하면, 기수 정렬의 시간 복잡도는 일반적으로 O(d * (n + k))입니다. 여기서 n은 정렬할 데이터의 개수이고 k는 각 자릿수에 있는 가능한 값의 수를 나타냅니다.

만약 데이터의 자릿수가 고정이라면 d는 상수이므로 시간 복잡도는 O(n + k)가 됩니다.
그러나 데이터의 자릿수가 가변적이라면 d는 n과 비슷한 크기가 될 수 있으며 이에 따라 시간 복잡도는 O(n * (n + k))까지도 될 수 있습니다.

코드

package io.github.ones1kk.study.sorting;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class RadixSort {

    public static int[] radixSort(int[] arr) {
        int maxDigit = getMaxDigit(arr);

        List<Queue<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            Queue<Integer> q = new LinkedList<>();
            bucket.add(q);
        }

        for (int digit = 0; digit < maxDigit; digit++) {
            for (int number : arr) {
                int bucketIdx = (number / (int) Math.pow(10, digit)) % 10;
                bucket.get(bucketIdx).add(number);
            }
            int arrIndex = 0;
            for (int i = 0; i < 10; i++) {
                Queue<Integer> q = bucket.get(i);
                int qSize = q.size();
                for (int j = 0; j < qSize; j++) {
                    arr[arrIndex] = q.poll();
                    arrIndex++;
                }
            }
        }
        return arr;
    }

    private static int getMaxDigit(int[] numbers) {
        int maxDigit = 0;
        for (int number : numbers) {
            int digit = (int) Math.log10(number) + 1;
            if (digit > maxDigit) {
                maxDigit = digit;
            }
        }
        return maxDigit;
    }

}

좀 더 자세한 코드는 이 곳에서 확인 가능합니다.

오탈자 및 오류 내용을 댓글 또는 메일로 알려주시면, 검토 후 조치하겠습니다.