[java] 기수 정렬 알고리즘의 동작 원리

15 Dec 2023

java

기수 정렬(Radix Sort) 알고리즘은 숫자를 자릿수를 기준으로 정렬하는 비교 기반 정렬 알고리즘입니다. 이 알고리즘은 자릿수를 하나씩 비교하여 정렬하는 것이 아니라, 각 자릿수마다 정렬하는 방식으로 동작하며, 안정적인 정렬 방법 중 하나입니다.

동작 원리

먼저 가장 작은 자릿수부터 가장 큰 자릿수까지 대상으로 정렬을 수행합니다.
각 자릿수에 해당하는 0부터 9까지의 버킷(또는 카운터)을 사용하여 정렬합니다.
입력된 숫자들을 해당하는 자릿수의 값에 따라 버킷에 나누어 넣습니다.
버킷에 들어 있는 숫자들의 순서를 유지한 채로 다시 원래 배열에 넣어줍니다.
가장 큰 자릿수까지 위 과정을 반복하여 정렬을 완료합니다.

public void radixSort(int[] arr) {
    int maxNumLength = getMaxNumLength(arr);
    for (int digit = 1; digit <= maxNumLength; digit++) {
        int[] tempArr = new int[arr.length];
        int[] count = new int[10];

        for (int num : arr) {
            int digitValue = getDigit(num, digit);
            count[digitValue]++;
        }

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

        for (int i = arr.length - 1; i >= 0; i--) {
            int digitValue = getDigit(arr[i], digit);
            tempArr[count[digitValue] - 1] = arr[i];
            count[digitValue]--;
        }

        System.arraycopy(tempArr, 0, arr, 0, arr.length);
    }
}

private int getMaxNumLength(int[] arr) {
    int max = 0;
    for (int num : arr) {
        int length = (int) Math.log10(num) + 1;
        if (length > max) {
            max = length;
        }
    }
    return max;
}

private int getDigit(int num, int digit) {
    return (num / (int) Math.pow(10, digit - 1)) % 10;
}

기수 정렬 알고리즘은 안정적이며, 정렬할 데이터의 수가 많을수록 효율적입니다. 이 알고리즘은 자릿수가 일정한 범위 내에 있을 때 가장 잘 작동하며, 음수가 포함되어 있을 경우 별도 처리가 필요합니다.

기수 정렬 알고리즘을 통해 정렬하고자 하는 숫자의 범위가 넓거나 정렬 대상이 정수일 때 효과적으로 사용할 수 있습니다.

참고 자료:

기수 정렬 알고리즘은 숫자를 자릿수를 기준으로 정렬하는 비교 기반 정렬 알고리즘입니다. 이 알고리즘은 자릿수를 하나씩 비교하여 정렬하는 것이 아니라, 각 자릿수마다 정렬하는 방식으로 동작하며, 안정적인 정렬 방법 중 하나입니다.

동작 원리

먼저 가장 작은 자릿수부터 가장 큰 자릿수까지 대상으로 정렬을 수행합니다.
각 자릿수에 해당하는 0부터 9까지의 버킷(또는 카운터)을 사용하여 정렬합니다.
입력된 숫자들을 해당하는 자릿수의 값에 따라 버킷에 나누어 넣습니다.
버킷에 들어 있는 숫자들의 순서를 유지한 채로 다시 원래 배열에 넣어줍니다.
가장 큰 자릿수까지 위 과정을 반복하여 정렬을 완료합니다.

public void radixSort(int[] arr) {
    int maxNumLength = getMaxNumLength(arr);
    for (int digit = 1; digit <= maxNumLength; digit++) {
        int[] tempArr = new int[arr.length];
        int[] count = new int[10];

        for (int num : arr) {
            int digitValue = getDigit(num, digit);
            count[digitValue]++;
        }

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

        for (int i = arr.length - 1; i >= 0; i--) {
            int digitValue = getDigit(arr[i], digit);
            tempArr[count[digitValue] - 1] = arr[i];
            count[digitValue]--;
        }

        System.arraycopy(tempArr, 0, arr, 0, arr.length);
    }
}

private int getMaxNumLength(int[] arr) {
    int max = 0;
    for (int num : arr) {
        int length = (int) Math.log10(num) + 1;
        if (length > max) {
            max = length;
        }
    }
    return max;
}

private int getDigit(int num, int digit) {
    return (num / (int) Math.pow(10, digit - 1)) % 10;
}

기수 정렬 알고리즘을 통해 정렬하고자 하는 숫자의 범위가 넓거나 정렬 대상이 정수일 때 효과적으로 사용할 수 있습니다.

참고 자료: