[java] 자바의 기수 정렬(Radix Sort) 알고리즘 이해하기

14 Dec 2023

java

기수 정렬은 숫자를 자릿수 별로 비교하여 정렬하는 알고리즘으로, 10진수의 경우 각 자릿수(일의 자리, 십의 자리, 백의 자리 등)를 기준으로 정렬합니다. 이 알고리즘은 정렬하려는 숫자들의 범위가 크지 않을 때 효과적입니다.

기수 정렬 알고리즘의 동작 원리

기수 정렬 알고리즘은 각 숫자의 자릿수를 비교하여 정렬합니다. 예를 들어, 숫자 135, 217, 425를 정렬할 때는 일의 자리부터 시작하여 각 자릿수의 크기를 비교하여 정렬합니다. 먼저, 일의 자리를 기준으로 정렬하고, 다음으로 십의 자리, 백의 자리 순으로 정렬합니다. 이 과정을 반복하여 모든 자릿수가 고려될 때까지 정렬을 계속합니다.

기수 정렬 알고리즘은 안정적인 정렬 알고리즘이며, 시간 복잡도는 O((n+b) * log_b(k))입니다. 여기서 n은 정렬할 숫자의 개수, k는 정렬할 숫자 중 가장 큰 값의 크기, b는 기수를 나타냅니다.

자바에서의 기수 정렬 구현

아래는 자바에서 기수 정렬 알고리즘을 구현한 예시 코드입니다.

import java.util.Arrays;

public class RadixSort {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(arr, exp);
        }
    }

    private static void countSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        Arrays.fill(count, 0);

        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

위 코드는 배열을 기수 정렬하는 radixSort 메서드와 기수 정렬을 위한 보조 메서드인 countSort를 포함하고 있습니다. radixSort 메서드를 호출하여 정렬된 배열을 얻을 수 있습니다.

기수 정렬은 숫자의 자릿수를 비교하여 정렬하기 때문에 정수형 데이터에 대해 주로 사용됩니다.

기수 정렬 알고리즘은 정렬할 데이터의 범위가 제한되어 있을 때 가장 효과적으로 동작하며, 자바에서도 효율적으로 구현할 수 있는 정렬 알고리즘 중 하나입니다.

참고 문헌:

Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
GeeksforGeeks: Radix Sort in Java (https://www.geeksforgeeks.org/radix-sort-in-java/)