[java] 기수 정렬 알고리즘

04 Dec 2023

java

기수 정렬(Radix Sort)은 비교 기반 정렬 알고리즘이 아닌 정렬 알고리즘입니다. 이 알고리즘은 자리수를 기준으로 정렬을 수행하는데, MSD(Most Significant Digit) 기수 정렬과 LSD(Least Significant Digit) 기수 정렬로 나뉩니다.

LSD(Lest Significant Digit) 기수 정렬

LSD 기수 정렬은 가장 낮은 자리수부터 시작하여 가장 높은 자리수까지 정렬을 수행하는 방식입니다. 이 알고리즘은 배열의 각 요소를 자릿수별로 선형적으로 비교하며 정렬을 진행합니다.

아래는 Java로 구현한 LSD 기수 정렬의 예제 코드입니다.

public class RadixSort {

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

    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

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

        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]--;
        }

        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

MSD(Most Significant Digit) 기수 정렬

MSD 기수 정렬은 가장 높은 자리수부터 시작하여 가장 낮은 자리수까지 정렬을 수행하는 방식입니다. 이 알고리즘은 각 자리수별로 재귀적으로 분할하며 정렬을 진행합니다.

MSD 기수 정렬을 구현하는 방법은 조금 복잡하며 여러 가지 경우를 처리해야 합니다. 자세한 구현은 생략하고, 아래는 MSD 기수 정렬의 예제 코드입니다.

public class RadixSort {

    public static void radixSort(int[] arr) {
        int max = getMax(arr);

        radixSort(arr, 0, arr.length - 1, max);
    }

    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    private static void radixSort(int[] arr, int left, int right, int digit) {
        if (left >= right || digit <= 0) {
            return;
        }

        int[] count = new int[10];
        int[] output = new int[right - left + 1];

        for (int i = left; i <= right; i++) {
            count[(arr[i] / digit) % 10]++;
        }

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

        for (int i = right; i >= left; i--) {
            output[count[(arr[i] / digit) % 10] - 1] = arr[i];
            count[(arr[i] / digit) % 10]--;
        }

        System.arraycopy(output, 0, arr, left, right - left + 1);

        for (int i = 0; i < 10; i++) {
            radixSort(arr, left + count[i], left + count[i + 1] - 1, digit / 10);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

LSD(Lest Significant Digit) 기수 정렬

MSD(Most Significant Digit) 기수 정렬

참고 자료