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

개요

기수 정렬(Radix Sort)은 정수형 데이터를 자릿수별로 분류하여 정렬하는 방식의 비교 기반이 아닌(non-comparative) 정렬 알고리즘이다. LSD(Least Significant Digit) 방식에서는 가장 낮은 자리부터 정렬하고, MSD(Most Significant Digit)는 가장 높은 자리부터 정렬한다. **시간 복잡도는 O(nk)**로 매우 효율적이며, 계수 정렬 또는 안정 정렬을 내부적으로 활용한다.

---

1. 개념 및 정의

기수 정렬은 숫자의 각 자릿수를 기준으로 여러 번의 정렬을 반복하여 전체 배열을 정렬하는 알고리즘이다. 각 자릿수마다 안정 정렬을 수행해야 정확한 결과를 보장할 수 있다.

예를 들어 [170, 45, 75, 90, 802, 24, 2, 66]를 정렬할 경우:

1. 1의 자리를 기준으로 정렬
2. 10의 자리를 기준으로 정렬
3. 100의 자리를 기준으로 정렬 → 최종적으로 정렬된 결과 도출

---

2. 동작 원리 (LSD 기준)

단계	설명
1단계	가장 낮은 자리(1의 자리)부터 정렬 시작
2단계	각 자리별로 안정 정렬(보통 계수 정렬)을 수행
3단계	다음 자리로 넘어가 반복
4단계	가장 높은 자리까지 모두 정렬하면 완료

LSD 방식은 일반적으로 구현이 간단하고 안정성이 높다.

---

3. 파이썬 구현 예시 (LSD 방식)

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    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

    return output

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

# 사용 예시
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

---

4. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(n × k) (k: 자릿수 길이)
공간 복잡도	O(n + k) (보조 배열 사용)

k가 작고 n이 클수록 매우 빠르며, 자릿수 기반 정렬이라 비교가 없다.

---

5. 특징 및 장단점

항목	설명
비교 기반 여부	X (값의 자릿수 기준 분류)
안정 정렬 여부	O (안정 정렬 사용 시)
실수 정렬	직접 불가 (정수 변환 필요)
음수 정렬	추가 로직 필요 (양수/음수 분리 등)
매우 빠름	정수 정렬에 이상적 조건 시 최고의 성능

---

6. 시각적 예시

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

• 1의 자리 기준 정렬: [170, 90, 802, 2, 24, 45, 75, 66]
• 10의 자리 기준 정렬: [802, 2, 24, 45, 66, 170, 75, 90]
• 100의 자리 기준 정렬: [2, 24, 45, 66, 75, 90, 170, 802] → 정렬 완료

---

7. 다른 정렬 알고리즘과 비교

알고리즘	시간 복잡도	공간 복잡도	비교 기반	안정 정렬	특징
기수 정렬	O(nk)	O(n + k)	X	O	빠르지만 정수 전용
계수 정렬	O(n + k)	O(k)	X	O	범위 작을 때 매우 빠름
퀵 정렬	O(n log n) 평균	O(log n)	O	X	빠르지만 최악 O(n²) 가능
병합 정렬	O(n log n)	O(n)	O	O	안정적, 대용량에 강함

---

8. 활용 사례

분야	활용 예시
정수형 로그 데이터 정렬	대용량 ID, 로그 번호 정렬
금융 데이터	거래 금액 등 범위 제한 정수 기반 정렬
알고리즘 대회	제한된 범위 정수형 입력에서 빠른 정렬 필요 시
통계 분석	범위 제한된 정수형 컬럼 정렬

---

9. 결론

기수 정렬은 비교 연산 없이 자릿수 정보를 활용해 정렬하는 매우 빠르고 효율적인 알고리즘이다. 조건이 맞을 경우 O(nk)의 성능으로 범용 비교 기반 정렬보다 훨씬 빠르게 작동하며, 안정 정렬이라는 장점도 갖는다. 다만 범위와 데이터 특성에 따라 적용 여부를 판단해야 하며, 정수 전용이라는 점을 반드시 고려해야 한다.