기수 정렬(Radix Sort) 알고리즘 구현하기

이번에는 자바로 기수정렬 알고리즘을 직접 구현해보겠습니다
이전에 사용했던 [170, 45, 75, 90, 802, 24, 2, 60] 배열을 오름차순 정렬할 것입니다

기수 정렬 알고리즘 구현 - Java

public static void main(String[] args){  
    int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};  
  
    radixSort(arr);  
  
    System.out.print(Arrays.toString(arr));
  
}  
  
private static void radixSort(int[] arr) {  
    int max = findMax(arr);  
  
    for (int i = 1; (max/i) > 0; i*=10) {  
        countDigit(arr, i);  
    }  
}  
  
private static void countDigit(int[] arr, int exp) {  
    int n = arr.length;  
    int[] res = new int[n];  
    int[] bucket = new int[10];  
    for (int i = 0; i < n; i++) {  
        int digit = (arr[i] / exp) % 10;  
        bucket[digit]++;  
    }  
  
    for (int i = 1; i < 10; i++) {  
        bucket[i] += bucket[i - 1];  
    }  
  
    for (int i = n-1; i >= 0; i--) {  
        int digit = (arr[i]/exp) % 10;  
        res[bucket[digit] - 1] = arr[i];  
        bucket[digit]--;  
    }  
  
    for (int i = 0; i < n; i++) {  
        arr[i] = res[i];  
    }  
}  
  
private static int findMax(int[] arr) {  
    int max = arr[0];  
    for (int i = 1; i < arr.length; i++) {  
        if (arr[i] > max) {  
            max = arr[i];  
        }  
    }  
    return max;  
}

위와같이 구현했습니다
동작 흐름은 이전에 정리한 동작방식과 유사합니다
먼저 최댓값을 찾고 그 값의 자릿수 만큼 순회하며, 정렬합니다

동작과정에서 살펴보지 못한 몇가지 로직이 추가되었는데 바로 누적합입니다
재배치하는 과정에서 각 버킷에 누적된 개수를 바탕으로
이번 기수정렬에서 몇번째 위치에 배치할지 정해집니다

안정배열을 보장하기 위해, 역순 탐색을 통해 배열을 재배치합니다
만약 순방향으로 탐색할 경우, 뒤에 있는 수가 먼저 배치되기 때문에,
역순으로 처리해서 먼저 배치되어있던 수를 새로운 배열에 배치하도록 해야합니다

역방향 탐색을 통해 안정 배열을 보장할 수 있습니다

결과 확인

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

위와같이 오름차순 정렬된 결과를 확인할 수 있습니다!