Counting Sort와 Radix Sort — 비교 없이 정렬하는 법

이진 트리의 높이 ≥ log₂(n!) = Θ(n log n)

원본: [4, 2, 2, 8, 3, 3, 1]
값 범위: 0~8

1. 카운트: count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
                     0  1  2  3  4  5  6  7  8

2. 누적합: count = [0, 1, 3, 5, 6, 6, 6, 6, 7]

3. 뒤에서부터 배치 (안정 정렬을 위해):
   arr[6]=1 → count[1]=1 → result[0]=1, count[1]=0
   arr[5]=3 → count[3]=5 → result[4]=3, count[3]=4
   ...

public static int[] countingSort(int[] arr, int maxVal) {
    int[] count = new int[maxVal + 1];
    int[] result = new int[arr.length];

    // 1. 각 값의 출현 횟수 세기
    for (int num : arr) {
        count[num]++;
    }

    // 2. 누적합 계산
    for (int i = 1; i <= maxVal; i++) {
        count[i] += count[i - 1];
    }

    // 3. 뒤에서부터 결과 배열에 배치 (안정 정렬)
    for (int i = arr.length - 1; i >= 0; i--) {
        result[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    return result;
}

원본:  [329, 457, 657, 839, 436, 720, 355]

1의 자리 정렬: [720, 355, 436, 457, 657, 329, 839]
10의 자리 정렬: [720, 329, 436, 839, 355, 457, 657]
100의 자리 정렬: [329, 355, 436, 457, 657, 720, 839]

public static void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();

    // 각 자릿수에 대해 Counting Sort 수행
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

private static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10]; // 0~9

    // 해당 자릿수 기준으로 카운트
    for (int num : arr) {
        int digit = (num / exp) % 10;
        count[digit]++;
    }

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

    // 뒤에서부터 배치 (안정 정렬)
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

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

public static void bucketSort(float[] arr) {
    int n = arr.length;
    List<List<Float>> buckets = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        buckets.add(new ArrayList<>());
    }

    // 값을 버킷에 분배 (0 이상 1 미만의 실수 가정)
    for (float num : arr) {
        int bucketIdx = (int) (num * n);
        buckets.get(bucketIdx).add(num);
    }

    // 각 버킷을 정렬
    for (List<Float> bucket : buckets) {
        Collections.sort(bucket);
    }

    // 버킷을 합치기
    int idx = 0;
    for (List<Float> bucket : buckets) {
        for (float num : bucket) {
            arr[idx++] = num;
        }
    }
}

// MSD Radix Sort: 높은 자릿수(첫 문자)부터 정렬
// 같은 첫 문자를 가진 문자열끼리 그룹을 만들고
// 각 그룹 내에서 두 번째 문자로 재귀적 정렬

// IP를 정수로 변환 후 Radix Sort
// 192.168.1.1 → 3232235777