초보 자바 프로그래밍(24) - 기수정렬 (Radix Sort)

기수 정렬 대표 이미지

🔖 INDEX

 

 

기수 정렬(Radix Sort)은 정수 및 문자열과 같은 비교가 아닌 데이터를 정렬하는 알고리즘입니다. 기수 정렬은 대표적으로 Least Significant Digit (LSD) 기수 정렬과 Most Significant Digit (MSD) 기수 정렬이 있습니다. 이 알고리즘은 각 자릿수의 값에 따라 데이터를 분류하고 정렬하는 방식을 사용합니다.

 

기수 정렬의 작동 원리

기수 정렬의 작동 원리는 다음과 같습니다.

 

Least Significant Digit (LSD) 기수 정렬

1. 가장 낮은 자릿수(일의 자리)부터 시작하여 각 숫자를 비교합니다.
2. 각 숫자를 해당 자릿수의 값에 따라 버킷(bucket)에 저장합니다.
3. 버킷에 저장된 숫자를 순서대로 다시 배열에 복사합니다.
4. 다음 자릿수로 넘어가 1- 3단계를 반복합니다.
5. 가장 높은 자릿수까지 처리한 후, 정렬이 완료됩니다. ​

 

Most Significant Digit (MSD) 기수 정렬

1. 가장 높은 자릿수부터 시작하여 각 숫자를 비교합니다.
2. 각 숫자를 해당 자릿수의 값에 따라 버킷에 저장합니다.
3. 버킷에 저장된 숫자를 순서대로 다시 배열에 복사합니다.
4. 다음 자릿수로 넘어가 1- 3단계를 반복합니다.
5. 가장 낮은 자릿수까지 처리한 후, 정렬이 완료됩니다.

 

 

기수 정렬의 특징

기수 정렬의 특징은 다음과 같습니다.

1. 비교 기반 정렬이 아님: 기수 정렬은 숫자의 자릿수를 이용하여 데이터를 분류하고 정렬하는 방식으로, 비교 기반 정렬 알고리즘과는 차별화된 방식을 사용합니다. 이를 통해 선형 시간 복잡도를 얻을 수 있습니다.
2. 안정 정렬: 기수 정렬은 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 유지되는 안정 정렬 알고리즘입니다. 이로 인해 데이터의 추가 정보를 유지하면서 정렬할 때 유용합니다.
3. 대량 데이터 처리에 적합: 기수 정렬은 선형 시간 복잡도를 가지므로, 대량의 데이터를 처리할 때 효율적입니다. 하지만 최대 자릿수에 따라 성능이 영향을 받으므로, 이 점을 고려해야 합니다.
4. 추가 메모리 사용: 기수 정렬은 버킷을 사용하여 데이터를 분류하고 정렬하는 과정에서 추가 메모리를 사용합니다. 이로 인해 메모리 제약이 있는 상황에서는 다른 정렬 알고리즘을 고려해야 할 수 있습니다.
5. 정수 및 문자열에 적합: 기수 정렬은 정수와 문자열과 같이 자릿수를 기반으로 분류할 수 있는 데이터 유형에 적합합니다. 반면 실수, 사용자 정의 객체 등의 데이터 유형에는 적용하기 어렵습니다. ​

 

기수 정렬의 장점

• 선형 시간 복잡도: 기수 정렬은 O(nk)의 시간 복잡도를 가집니다. 여기서 n은 데이터의 개수이고 k는 최대 자릿수입니다. 비교 기반 정렬 알고리즘보다 빠른 성능을 보입니다.
• 안정성: 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 유지됩니다. ​

 

기수 정렬의 단점

• 제한된 데이터 유형: 기수 정렬은 정수, 문자열 등의 비교가 아닌 데이터 유형에만 적용 가능합니다. 실수, 사용자 정의 객체 등의 데이터 유형에는 적용하기 어렵습니다.
• 추가 메모리 사용: 버킷에 데이터를 저장하기 위해 추가 메모리가 필요합니다.

 

 

기수 정렬의 구현 예제

기수 정렬은 자바에서 다음과 같이 구현할 수 있습니다. (LSD 기반)

// RadixSort 클래스 선언
public class RadixSort {
    // 기수 정렬 알고리즘을 수행하는 함수
    public static void radixSort(int[] arr) {
        int max = getMax(arr); // 배열의 최대값을 찾음
        // 1의 자리부터 최대 자릿수까지 반복하여 계수 정렬 수행
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    // 배열에서 최대값을 찾는 함수
    private 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;
    }

    // 기수 정렬에서 각 자릿수에 대해 계수 정렬을 수행하는 함수
    private static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 정렬된 결과를 저장할 배열
        int[] count = new int[10]; // 각 자릿수의 빈도를 저장할 배열
        Arrays.fill(count, 0); // count 배열을 0으로 초기화

        // 각 원소의 해당 자릿수를 기준으로 빈도를 셈
        for (int i = 0; i < n; i++) {
            int index = (arr[i] / exp) % 10;
            count[index]++;
        }

        // 누적 합을 계산하여 count 배열을 업데이트
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // output 배열에 원소를 올바른 위치에 넣음
        for (int i = n - 1; i >= 0; i--) {
            int index = (arr[i] / exp) % 10;
            output[count[index] - 1] = arr[i];
            count[index]--;
        }

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

기수 정렬은 특정한 데이터 유형에만 적용 가능하므로, 정렬하려는 데이터 유형이 기수 정렬에 적합한지 확인해야 합니다. 또한 최대 자릿수에 따라 알고리즘의 성능이 크게 영향을 받으므로, 자리 속성을 고려하여 알고리즘의 성능을 평가해야 합니다. ​

 

기수 정렬은 각 자릿수에 대한 버킷을 준비하고, 각 자릿수별로 데이터를 분류하고 정렬하는 방식으로 동작하므로, 어떤 방식의 기수 정렬 알고리즘을 사용하는지에 따라 성능 차이가 발생할 수 있습니다. 예를 들어, LSD 기수 정렬은 가장 낮은 자릿수부터 시작하여 정렬을 수행하는 반면, MSD 기수 정렬은 가장 높은 자릿수부터 시작하여 정렬을 수행합니다. 이러한 차이점을 고려하여 데이터의 특성에 따라 적절한 기수 정렬 알고리즘을 선택하는 것이 중요합니다. ​

 

또한, 기수 정렬은 각 자릿수의 범위가 클수록 버킷의 개수가 많아지므로, 메모리 사용량이 늘어납니다. 따라서 메모리 사용량에 대한 고려도 필요합니다. ​

 

결론적으로, 기수 정렬은 선형 시간 복잡도를 가진 빠른 정렬 알고리즘이지만, 데이터 유형과 자릿수의 특성에 따라 성능이 크게 달라질 수 있습니다. 이러한 특성을 고려하여 적절한 정렬 알고리즘을 선택하는 것이 중요합니다.