선택 심화: 자릿수·버킷·기수 정렬

정렬할 값이 음수가 아닌 정수라면 비교 대신 자릿수를 사용할 수 있습니다. 목표는 낮은 자리부터 처리해도 전체 순서가 만들어지는 이유와 버킷 내부 순서의 필요성을 이해하는 것입니다. 정수 나머지와 안정 정렬을 복습하세요.

개념과 약속

기수는 숫자 표현의 밑입니다. 10진수의 각 자리 값은 0~9입니다. place=1은 일의 자리, 10은 십의 자리이며 (value//place)%10으로 뽑습니다. LSD 기수 정렬은 낮은 자리부터 시작합니다. 버킷은 같은 자리 값을 가진 원소의 묶음이고 0부터 9까지 순서대로 연결합니다.

같은 버킷에서는 들어온 순서를 보존해야 앞서 정렬한 낮은 자리 순서가 유지됩니다. 자릿수가 적은 수에서 빠진 높은 자리는 0으로 봅니다. 이 구현은 음수가 아닌 Python 정수만 받으며 음수·실수·bool은 거부합니다. 문자도 코드로 표현할 수 있지만 고정 길이 문자열의 자릿수 처리와 사전식 언어 정렬·유니코드 정규화는 별도 설계가 필요합니다. 숫자 버킷 코드를 문자열에 그대로 붙이지 않습니다.

손으로 상태 추적하기

십의 자리 1인 12·13이 일의 자리 순서를 그대로 유지합니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def radix_sort(values):
    if any(type(value) is not int or value < 0 for value in values):
        raise ValueError("nonnegative integers required")
    result = list(values)
    place, largest = 1, max(result, default=0)
    while largest // place:
        buckets = [[] for _ in range(10)]
        for value in result:
            buckets[(value // place) % 10].append(value)
        result = [value for bucket in buckets for value in bucket]
        place *= 10
    return result


print(radix_sort([21, 13, 12, 3]))
print(radix_sort([0, 10, 0, 1]))
print(radix_sort([]))
try:
    radix_sort([-1, 2])
except ValueError:
    print("음수 거부")

실행 결과:

[3, 12, 13, 21]
[0, 0, 1, 10]
[]
음수 거부

왜 맞고 언제 끝나는가

한 자리를 처리한 뒤 그 자리까지의 낮은 자릿수 전체에 대해 정렬됩니다. 다음 높은 자리로 묶어도 같은 높은 자리 안에서 안정성이 이전 낮은 자리 순서를 보존합니다. 가장 높은 자리까지 처리하면 전체 숫자 순서가 됩니다. place는 10배씩 커져 최댓값보다 커지면 끝납니다.

비용과 적용 범위

최대 자릿수 d, 기수 b에서 O(d(n+b)) 시간, O(n+b) 버킷 공간입니다. 여기 b=10입니다. 자릿수가 커지는 비용을 생략해 무조건 O(n)이라고 말하지 않습니다. 비교 정렬 하한과도 모델·입력 조건이 다릅니다.

스스로 풀어 보기

1. [32,21,12]를 일의 자리를 처리한 뒤 목록을 쓰세요.
2. 십의 자리 버킷 안에서 입력 순서를 뒤집으면 [12,13]에 어떤 오류가 생기나요?

힌트

1. 자리값 1과 2를 나눕니다.
2. 높은 자리 동률 안에 남은 낮은 자리 순서가 필요합니다.

해설

1. [21,32,12]입니다. 일의 자리가 2인 32,12의 원래 순서를 보존합니다.
2. 같은 십의 자리 버킷에서 13,12가 되어 전체 오름차순이 깨집니다.

흔한 오해

기수 정렬은 모든 종류의 비교 가능한 객체를 다룬다는 보장이 없습니다. 음수 처리, 고정·가변 길이, 문자 순서마다 명세를 확장해야 합니다.

복습과 다음 연결

외부 정렬은 숫자 성질보다 메모리·파일의 제약을 다룹니다.