[알고리즘] 기수 정렬(Radix Sort)

계수정렬에 이어 기수정렬도 정리하려고 한다.

기수정렬(Radix Sort)

기수 정렬은 같은 키 값을 가진 데이터의 상대적인 순서를 유지하는 정렬 알고리즘이다.
"기수"는 숫자의 자릿수를 의미하며, 자리수에 따라 정렬을 수행하는 방식에서 유래되었다고 한다.
기수정렬은 비비교 정렬 알고리즘이다. 따라서 정수나 유한한 범위의 데이터를 대상으로 하고,

기수정렬은 자리수를 기준으로 정렬되며, 안정적인 정렬방식으로 같은 값을 가진 요소의 상대적 순서는 유지된다.
정수범위가 좁고(자리수), 양이 많은 데이터일 경우 유리하다.

기수정렬의 시간복잡도

최악의 경우 시간 복잡도는 O(d*(n + k))이다.
여기서 n은 정렬할 요소의 수, d는 최대 자리수, k는 기수(base)를 의미한다.

기수정렬 원리

기수정렬은 가장 낮은 자리수(LSB)에서부터 시작하여 가장 높은 자리수(MSB)까지 정렬을 수행한다.

 

[170, 45, 75, 90, 802, 24, 2]를 정렬하는 과정을 살펴보자.

1. 가장 낮은 자리수부터 정렬하기

우리의 예시에서는 1의 자리수부터 100의 자리수까지 정렬하면 된다. 

 

그러면,

주어진 배열은 [170, 45, 75, 90, 802, 24, 2].

1의 자리수: 0, 5, 5, 0, 2, 4, 2
0: 170, 90
5: 45, 75
2: 802, 2
4: 24
정렬 결과(1의 자리수 기준): [170, 90, 45, 75, 802, 2, 24] 이 된다.

 

170과 90같은 경우, 두 개의 동일한 값이 있을 때, 원래의 순서가 정렬 후에도 그대로 유지되는 특성이 있기 때문에 기존 순서를 유지한다.

 

2. 10의 자리수 정렬하기

1의 자리수를 비교했으니 이번에는 10의 자리수를 비교한다.

 

1의 자리수 기준은 [170, 90, 45, 75, 802, 2, 24] 였다.

여기서 2의 10의 자리수는 0이 라고 생각하면 된다. 그러면,

 

10의 자리수: 7, 9, 4, 7, 0, 0, 2
0: 802, 2
2: 24
4: 45
7: 170, 75
9: 90
정렬 결과(10의 자리수 기준): [802, 2, 24, 45, 170, 75, 90] 

 

3. 100의 자리수 정렬하기

10의 자리수를 비교한 결과 [802, 2, 24, 45, 170, 75, 90] 를 가지고 100의 자리수를 비교해보자.

마찬가지로 100의 자리수가 없는 숫자 2, 24, 45, 75, 90은 100의  자리수가 0이다.

100의 자리수: 8, 0, 0, 0, 1, 0, 0
0: 2, 24, 45, 75, 90
1: 170
8: 802
그러면 최종 정렬 결과(100의 자리수 기준): [2, 24, 45, 75, 90, 170, 802]이 된다.

 

 

코드구현

Java

import java.util.Arrays;

public class RadixSort {
    // 주어진 배열의 가장 큰 값을 찾는 메서드
    public 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;
    }

    // 주어진 배열을 특정 자리수에 따라 정렬하는 메서드
    public static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // 0-9까지의 숫자이므로 크기는 10

        // 자리수에 대한 카운트 배열 초기화
        Arrays.fill(count, 0);

        // 해당 자리수에 대한 카운트
        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]--;
        }

        // 원래 배열에 정렬된 값 복사
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    // Radix Sort 메서드
    public static void radixSort(int[] arr) {
        int max = getMax(arr);

        // 자리수에 따라 정렬
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2};
        radixSort(arr);
        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

 

Javascript

function getMax(arr) {
    return Math.max(...arr);
}

function countingSort(arr, exp) {
    const n = arr.length;
    const output = new Array(n);
    const count = new Array(10).fill(0);

    // 자리수에 대한 카운트
    for (let i = 0; i < n; i++) {
        count[Math.floor(arr[i] / exp) % 10]++;
    }

    // 카운트를 누적합으로 변환
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 출력 배열에 정렬된 값 저장
    for (let i = n - 1; i >= 0; i--) {
        output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
        count[Math.floor(arr[i] / exp) % 10]--;
    }

    // 원래 배열에 정렬된 값 복사
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

function radixSort(arr) {
    const max = getMax(arr);

    // 자리수에 따라 정렬
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

// 사용 예시
const arr = [170, 45, 75, 90, 802, 24, 2];
radixSort(arr);
console.log("정렬된 배열:", arr);