기수 정렬 알고리즘 원리, 코드, 시간 복잡도

기수 정렬이 해결하는 문제

계수 정렬은 선형이지만 전체 키 범위만큼 큰 계수 배열이 필요해서 32비트나 64비트 정수에는 쓸 수 없습니다. 기수 정렬은 각 키를 작은 자릿수로 나누어 자릿수마다 계수 정렬을 한 번씩 실행하므로, 각 패스에는 b개 항목의 계수 배열(10진수 자릿수면 10개, 바이트면 256개)만 있으면 됩니다.

작은 기호들의 고정된 나열로 쪼갤 수 있는 키라면 무엇이든 가능합니다. 음이 아닌 정수, YYYYMMDD로 쓴 날짜, 우편번호 같은 고정 길이 코드, IP 주소, 고정 폭 문자열 등입니다.

예제: 10진법 LSD 기수 정렬

[170, 45, 75, 90, 802, 24, 2, 66]을 정렬해 봅시다. 가장 큰 수가 3자리이므로 패스는 3번입니다. 각 패스는 한 자릿수에 대한 안정 정렬이므로, 자릿수가 같은 요소는 이전 패스의 순서를 유지합니다.

2번째 패스 후에는 숫자가 마지막 두 자리 기준으로 정렬되어 있습니다. 3번째 패스에서 2, 24, 45, 66, 75, 90은 모두 백의 자리가 0이고, 안정성 덕분에 2번째 패스가 만든 순서가 유지됩니다. 그래서 각 패스는 반드시 안정적이어야 합니다.

파이썬 구현

def counting_pass(nums, exp, base):
    """Stable counting sort of nums by the digit at exp."""
    count = [0] * base
    for x in nums:
        count[(x // exp) % base] += 1
    for d in range(1, base):
        count[d] += count[d - 1]
    out = [0] * len(nums)
    for x in reversed(nums):
        d = (x // exp) % base
        count[d] -= 1
        out[count[d]] = x
    return out

def radix_sort(nums, base=10):
    """LSD radix sort for non-negative integers."""
    if not nums:
        return []
    exp, biggest = 1, max(nums)
    while biggest // exp > 0:
        nums = counting_pass(nums, exp, base)
        exp *= base
    return nums

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(radix_sort([3, 0, 1, 0], base=256))   # [0, 0, 1, 3]

256진법을 쓰면 패스마다 한 바이트씩 보므로 32비트 정수는 4번의 패스면 충분합니다. 음수를 포함하려면 음수와 음이 아닌 값을 따로 정렬해 이어 붙이거나 모든 키를 최솟값만큼 이동시키세요. 고정 길이 문자열에는 위치 i의 문자 코드를 자릿수로 쓰고 마지막 위치에서 첫 위치 방향으로 진행하세요.

시간 복잡도와 공간 복잡도

d가 상수(고정 폭 키)이고 b를 n에 가깝게 또는 256 같은 고정 값으로 잡으면 시간은 O(n)입니다. n개의 키가 모두 서로 다르면 d는 최소 log_b n이어야 하므로, 임의 크기의 키에서는 기수 정렬이 O(n log n)을 넘어서지 못합니다. 그래도 빠른 이유는 각 단계가 단순한 배열 연산이기 때문입니다.

기수 정렬과 다른 정렬 비교

표에서 n은 키의 수, k는 계수 정렬의 키 범위, d는 자릿수, b는 진법입니다. LSD 기수 정렬은 모든 자릿수 패스가 안정적이기만 하면 안정 정렬입니다. 키가 고정된 구조여야 하지만, 병합 정렬과 퀵 정렬 같은 비교 정렬은 사용자 정의 비교 함수를 포함해 어떤 순서에도 쓸 수 있습니다.

LSD와 MSD, 그리고 흔한 실수

기수 정렬을 쓰는 경우

32비트 ID, 타임스탬프, IPv4 주소, 고정 길이 문자열처럼 고정 폭 정수나 키로 이루어진 큰 배열에 잘 맞으며, 규칙적인 메모리 접근이 효과를 내는 GPU와 고성능 라이브러리에서 특히 그렇습니다. 접미사 배열 구성과 일부 데이터베이스·그래픽스 작업에도 쓰입니다. 일반 파이썬 리스트에서는 sorted()가 최적화된 C 코드로 실행되므로 실제로는 거의 항상 더 빠릅니다. 면접에서는 선형 시간에 정렬하는 방법을 물을 때, 예를 들어 Maximum Gap 문제에서 기수 정렬이 등장합니다.