[java] 기수 정렬 알고리즘

14 Dec 2023

java

기수 정렬 알고리즘은 비교 정렬 알고리즘과 달리 숫자의 비교를 사용하지 않고 자리수를 기준으로 정렬하는 알고리즘입니다. 대부분의 정렬 알고리즘보다 빠르며, 특히 숫자를 정렬할 때 유용합니다.

기수 정렬 알고리즘의 동작

각 자릿수(일의 자리, 십의 자리, 백의 자리 등)를 기준으로 정렬하는 과정을 반복합니다.
각 자릿수를 기준으로 숫자들을 버킷에 나누어 담습니다.
버킷에 담긴 숫자들을 순서대로 다시 모아 정렬합니다.
가장 큰 자릿수가 모두 정렬될 때까지 반복합니다.

기수 정렬 알고리즘의 예시 코드

public class RadixSort {
    public static void radixSort(int[] arr) {
        int max = getMax(arr);
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }

    private static void countingSort(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10];
        for (int i : arr) {
            count[(i / exp) % 10]++;
        }
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }
}

위의 코드는 기수 정렬을 구현한 Java 예시입니다.

기수 정렬 알고리즘의 시간 복잡도

기수 정렬 알고리즘은 입력되는 숫자의 자릿수에 따라 시간 복잡도가 결정됩니다. 만약 입력된 숫자의 최대 자릿수를 k, 입력된 숫자의 개수를 n이라고 할 때, 기수 정렬 알고리즘의 시간 복잡도는 O(kn)입니다.

기수 정렬은 숫자를 정렬하는 효율적인 알고리즘 중 하나로, 대용량 숫자 데이터를 빠르게 정렬할 수 있는 장점이 있습니다.

기수 정렬 알고리즘과 다른 정렬 알고리즘의 비교에 대한 더 자세한 정보는 여기에서 확인할 수 있습니다.