정렬 알고리즘 (Sorting Algorithms) - 기수 정렬 (Radix Sort)

기수 정렬 (Radix Sort)

기수 정렬은 비교 기반이 아닌 정렬 알고리즘으로, 숫자의 자릿수를 기준으로 가장 작은 자릿수부터 가장 큰 자릿수까지 정렬합니다. 정수 또는 고정된 길이의 문자열과 같은 데이터를 정렬하는 데 적합합니다.

---

1. 동작 원리

1. 최대 자릿수 확인: 데이터 중 가장 큰 값의 자릿수를 확인합니다.
2. 자릿수별 정렬:
   • 가장 작은 자릿수(1의 자리)부터 시작해 각 자릿수를 기준으로 안정적인 정렬(예: 계수 정렬)을 수행합니다.
   • 이후 10의 자리, 100의 자리 등 큰 자릿수로 이동하며 정렬을 반복합니다.
3. 정렬 완료: 모든 자릿수를 기준으로 정렬이 끝나면 데이터는 정렬된 상태가 됩니다.

---

2. 특징

• 시간 복잡도:
  • O(d x (n + k)), 여기서:
    • d: 가장 큰 값의 자릿수
    • n: 배열의 크기
    • k: 자릿수의 범위 (일반적으로 0–9)
• 공간 복잡도: O(n + k) (계수 배열과 출력 배열에 추가 메모리 사용)
• 안정성: 기수 정렬은 안정적입니다. 즉, 값이 같은 요소의 상대적인 순서는 유지됩니다.
• 제한 사항:
  • 정수 또는 고정된 형식의 데이터에만 적용 가능.
  • 자릿수가 많거나 범위가 큰 경우 비효율적일 수 있음.

---

3. 정렬 과정

입력 배열: [170, 45, 75, 90, 802, 24, 2, 66]

1. 1의 자릿수 정렬:
   • 자릿수를 기준으로 정렬 후: [170, 802, 2, 24, 45, 75, 66, 90]
2. 10의 자릿수 정렬:
   • 자릿수를 기준으로 정렬 후: [802, 2, 24, 45, 66, 170, 75, 90]
3. 100의 자릿수 정렬:
   • 자릿수를 기준으로 정렬 후: [2, 24, 45, 66, 75, 90, 170, 802]

최종 정렬된 배열: [2, 24, 45, 66, 75, 90, 170, 802]

---

4. 장단점

장점:

1. 선형 시간 복잡도: 작은 자릿수를 가진 데이터에서는 매우 효율적입니다.
2. 비교 기반이 아님: 요소 간의 직접적인 비교를 피합니다.

단점:

1. 추가 메모리 사용: 중간 결과를 저장하기 위해 추가 공간이 필요합니다.
2. 적용 한계: 숫자 또는 고정된 길이의 문자열 정렬에만 적합합니다.

---

5. Java 구현

import java.util.Arrays;

public class RadixSort {

    // 배열에서 최대값 찾기
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    // 현재 자릿수(exp)를 기준으로 계수 정렬
    private static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // 0-9까지의 자릿수

        // 자릿수별 개수 세기
        for (int num : arr) {
            count[(num / exp) % 10]++;
        }

        // 누적 합 계산
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 출력 배열에 정렬된 값 배치
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 원본 배열에 출력 배열 복사
        System.arraycopy(output, 0, arr, 0, n);
    }

    // 기수 정렬 메서드
    public static void radixSort(int[] arr) {
        int max = getMax(arr);

        // 1의 자리부터 시작해 모든 자릿수에 대해 정렬 수행
        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, 66};
        System.out.println("원본 배열: " + Arrays.toString(arr));

        radixSort(arr);

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

---

6. Python 구현

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 자릿수 범위: 0-9

    # 자릿수별 개수 세기
    for num in arr:
        index = (num // exp) % 10
        count[index] += 1

    # 누적 합 계산
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 출력 배열에 정렬된 값 배치
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # 원본 배열에 출력 배열 복사
    for i in range(n):
        arr[i] = output[i]


def radix_sort(arr):
    # 배열에서 최대값 확인
    max_val = max(arr)

    # 모든 자릿수에 대해 정렬 수행
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10


# 예제 실행
if __name__ == "__main__":
    arr = [170, 45, 75, 90, 802, 24, 2, 66]
    print("원본 배열:", arr)

    radix_sort(arr)

    print("정렬된 배열:", arr)

---

7. 언제 사용해야 하나?

1. 자릿수가 작은 정수 배열:
   • 정렬할 데이터의 자릿수가 적고 범위가 작을 때 매우 효율적입니다.
2. 정수 데이터 정렬:
   • 숫자를 대상으로 직접 비교하지 않아 빠른 정렬이 가능합니다.
3. 고정 길이 문자열:
   • 문자열을 정렬할 때도 응용 가능하며, 자릿수를 문자로 취급해 정렬합니다.

기수 정렬은 특정 시나리오에서 매우 강력한 도구로, 특히 정수 또는 고정된 포맷의 데이터에 적합합니다.