기수 정렬 (Radix Sort)

구현 코드 예시

def counting_sort_by_digit(arr, exp):
    """exp 자릿수(1, 10, 100…)를 기준으로 안정 정렬한다."""
    n = len(arr)
    output = [0] * n
    count = [0] * 10                     # 0~9 열 칸이면 충분하다

    for v in arr:
        count[(v // exp) % 10] += 1

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

    for v in reversed(arr):              # 뒤에서부터 — 안정성의 핵심
        digit = (v // exp) % 10
        count[digit] -= 1
        output[count[digit]] = v

    return output


def radix_sort(arr):
    if not arr:
        return arr

    exp = 1
    max_v = max(arr)
    while max_v // exp > 0:              # 최댓값의 자릿수만큼 반복
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

(v // exp) % 10이 자릿수를 뽑는 관용구다. exp=1이면 1의 자리, exp=10이면 10의 자리가 나온다. 반복 조건을 max_v // exp > 0으로 두면 최댓값의 자릿수만큼만 돌고 자동으로 멈춘다.

한계와 대안

• 음수를 그대로 다루지 못한다. 자릿수 추출이 음수에서 깨진다. 음수와 양수를 분리해 각각 정렬한 뒤, 음수 쪽은 뒤집어서 앞에 붙이는 방법을 쓴다.
• 실수에 쓰기 어렵다. 소수점 이하 자릿수가 정해져 있지 않으면 d가 무한해진다.
• 메모리를 계속 쓴다. 자릿수마다 출력 배열을 새로 만든다. 제자리 정렬이 아니다.
• 문자열에는 쓸 수 있다. 길이가 같은 문자열이라면 마지막 글자부터 같은 방식으로 정렬하면 사전순 정렬이 된다.

코딩테스트에서 기수 정렬을 직접 구현해 제출할 일은 거의 없다. 다만 "정렬을 O(n)에 하라"거나 "비교 연산을 쓰지 말라"는 제약이 붙으면 계수 정렬과 함께 후보에 올려야 한다.

자주 하는 실수

• 불안정 정렬을 부품으로 쓴다. 각 단계에 퀵 정렬 같은 불안정 정렬을 쓰면 이전 자릿수 순서가 무너져 결과가 틀린다. 기수 정렬의 전제가 깨지는 것이라 부분적으로 맞는 답조차 안 나온다.
• 높은 자리부터 정렬한다. LSD 방식에서 순서를 뒤집으면 아래 자리가 위 자리를 덮어써서 완전히 틀린 결과가 나온다.
• 반복 횟수를 잘못 잡는다. 원소 개수가 아니라 최댓값의 자릿수만큼 돌아야 한다.
• 계수 정렬 단계에서 정방향으로 읽는다. reversed(arr)를 빼면 안정성이 깨져 위와 같은 문제가 생긴다.
• 음수를 그냥 넣는다. 파이썬에서 (-45 // 10) % 10은 예상과 다른 값을 낸다. 별도 처리가 필요하다.

면접에서 이렇게 물어본다

• 기수 정렬이 낮은 자리부터 정렬하는 이유를 설명해 보라.
• 각 단계에 반드시 안정 정렬을 써야 하는 이유는 무엇인가.
• 계수 정렬과 기수 정렬의 관계는 무엇인가.
• 기수 정렬이 O(n)에 가까운데도 기본 정렬로 쓰이지 않는 이유는 무엇인가.
• 음수가 포함된 배열은 어떻게 처리하겠는가.
• 문자열 정렬에 기수 정렬을 적용할 수 있는가.