기수 정렬

기수 정렬은 비교 기반 정렬 알고리즘이 아닌, 자릿수를 이용하여 정렬하는 안정적인 정렬 알고리즘 중 하나이다. 주로 정수나 문자열과 같이 각 자리의 의미가 있는 데이터를 정렬할 때 사용된다.

가장 낮은 자리수부터 정렬하고 한 자릿수가 정렬되면 다음 자릿수로 이동하여 같은 과정을 반복한다.시간 복잡도는 O(k*n)으로 정수나 문자열의 자리수 * 배열의 크기이다.

 

우선순위 큐를 이용한 방법

import java.util.PriorityQueue;

public class RadixSortWithPriorityQueue {

    public static void radixSort(int[] arr) {
        // 가장 큰 자리수의 수 찾기
        int maxDigit = getMaxDigit(arr);

        // 각 자리수에 대해 우선순위 큐 사용하여 정렬
        for (int digit = 1; digit <= maxDigit; digit *= 10) {
            countingSortWithPriorityQueue(arr, digit);
        }
    }

    private static int getMaxDigit(int[] arr) {
        int max = arr[0];
        for (int value : arr) {
            if (value > max) {
                max = value;
            }
        }
        return (int) Math.log10(max) + 1; // 가장 큰 자리수 구하기
    }

    private static void countingSortWithPriorityQueue(int[] arr, int digit) {
        int n = arr.length;
        PriorityQueue<Integer>[] buckets = new PriorityQueue[10];

        for (int i = 0; i < 10; i++) {
            buckets[i] = new PriorityQueue<>();
        }

        // 각 자리수에 따라 숫자를 버킷에 넣기
        for (int value : arr) {
            int digitValue = (value / digit) % 10;
            buckets[digitValue].offer(value);
        }

        // 버킷에서 숫자를 꺼내어 배열에 저장
        int index = 0;
        for (PriorityQueue<Integer> bucket : buckets) {
            while (!bucket.isEmpty()) {
                arr[index++] = bucket.poll();
            }
        }
    }
}

 

계수 정렬을 이용하여 정렬

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 value : arr) {
            if (value > max) {
                max = value;
            }
        }
        return max;
    }

    // 계수 정렬을 사용
    private static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] tmp = new int[n];
        int[] count = new int[10]; // 0부터 9까지의 숫자를 세기 위한 배열

        // 각 자리수의 개수 세기
        for (int value : arr) {
            count[(value / exp) % 10]++;
        }

        // 누적 합 구하기
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 배열을 역순으로 돌면서 tmp 배열에 정렬된 순서대로 저장
        for (int i = n - 1; i >= 0; i--) {
            // 정렬하게될 자리에 숫자
            int num = (arr[i] / exp) % 10;
            tmp[count[num] - 1] = arr[i];
            count[num]--;
        }

        // tmp 배열을 원래 배열로 복사
        System.arraycopy(tmp, 0, arr, 0, n);
    }

}