9월 3일 - 기수정렬

기수 정렬(Radix Sort)

기수 정렬(Radix Sort)은 데이터의 자릿수를 기준으로 정렬하는 알고리즘입니다. 이 정렬 방법은 자릿수를 기준으로 데이터를 여러 번 정렬하여 최종적으로 정렬된 결과를 얻습니다. 주로 정수 정렬에 사용되며, 정렬할 숫자의 자릿수에 따라 효율적으로 작동합니다.

기수 정렬의 기본 개념

기수 정렬은 숫자의 각 자릿수를 기준으로 정렬을 반복적으로 수행합니다. 먼저 가장 낮은 자릿수부터 시작하여 높은 자릿수로 이동하며 정렬을 수행합니다. 기수 정렬은 안정적인 정렬 알고리즘이며, 시간 복잡도는 O(d * (n + b))입니다. 여기서 d는 정렬할 숫자의 자릿수, n은 배열의 크기, b는 숫자 기수(예: 10진수일 경우 10)를 나타냅니다.

구현 방법

Java로 구현한 기수 정렬 코드는 다음과 같습니다:

import java.util.Arrays;

public class RadixSort {

    // 주어진 배열에서 최대값을 반환하는 함수
    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;
    }

    // Counting Sort 함수, exp는 현재 자릿수를 나타냄
    private static void countSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 정렬된 배열을 저장할 배열
        int[] count = new int[10]; // 자릿수 별로 카운트를 저장할 배열

        // 자릿수에 따른 카운트 증가
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

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

        // Counting Sort를 수행
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // 결과를 원래 배열에 복사
        System.arraycopy(output, 0, arr, 0, n);
    }

    // Radix Sort 함수
    private static void radixSort(int[] arr) {
        int max = getMax(arr); // 최대 자릿수를 구함

        // 각 자릿수별로 Counting Sort 수행
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(arr, exp);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

        radixSort(arr);

        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

설명

• getMax: 배열에서 최대값을 구하여 가장 높은 자릿수를 판단하는 함수입니다. 기수 정렬은 이 최대 자릿수를 기준으로 정렬을 진행합니다.
• countSort: 현재 자릿수에 해당하는 숫자들에 대해 카운팅 정렬을 수행하는 함수입니다. 각 자릿수별로 정렬을 하여 최종적으로 정렬된 결과를 얻습니다.
• radixSort: 기수 정렬의 메인 함수로, 자릿수별로 카운팅 정렬을 호출하여 전체 배열을 정렬합니다.
• main: 정렬할 배열을 정의하고 radixSort 함수를 호출하여 결과를 출력합니다.

So...

기수 정렬은 특정 자릿수로 숫자들을 분류하여 정렬하는 알고리즘으로, 숫자 정렬에 매우 유용합니다. 특히, 큰 범위의 정수를 정렬할 때 효과적이며, 안정적인 정렬을 제공합니다. 하지만, 중간 결과를 저장하기 위한 추가 메모리 공간이 필요하다는 단점도 있습니다. 이러한 점들을 고려하여 기수 정렬을 적절한 상황에 사용하는 것이 중요합니다.