기수 정렬

각 자릿수(1의 자리 → 10의 자리 → …)를 기준으로 계수 정렬을 반복 적용하는 정렬로, 자릿수 d가 고정이면 O(n)이 가능합니다.

동작 과정

[170, 45, 75, 90, 802, 24, 2, 66]

1의 자리 기준 정렬:
→ [170, 90, 802, 2, 24, 45, 75, 66]

10의 자리 기준 정렬:
→ [802, 2, 24, 45, 66, 170, 75, 90]

100의 자리 기준 정렬:
→ [2, 24, 45, 66, 75, 90, 170, 802]

구현

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

    for (int exp = 1; max / exp > 0; exp *= 10)
        countByDigit(arr, exp);
}

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

    for (int x : arr) count[(x / exp) % 10]++;
    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]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, n);
}

복잡도

• d = 자릿수, k = 각 자리 값 범위 (보통 10)
• 안정 정렬 O (각 단계에서 계수 정렬 사용)

계수 정렬 vs 기수 정렬

→ 정렬