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

입력 크기·O·Ω·Θ와 정보의 개수에서, 값끼리 비교해서만 정렬하는 방법은 최악의 경우 약 n log₂ n번보다 적게 비교할 수 없다는 것을 보았습니다. 그런데 이 한계는 "비교만으로 정렬한다"는 조건에서 나온 것입니다. 정렬할 값이 0 이상인 정수라면, 값을 비교하는 대신 값 자체를 보고 어느 칸에 넣을지 정할 수 있고, 그러면 이 한계에 묶이지 않습니다. 이 글에서는 값의 범위가 작을 때 쓰는 계수 정렬에서 시작해, 자릿수를 하나씩 이용하는 기수 정렬을 만들고, 이 방법들이 어떤 입력에서 빠르고 어떤 조건이 필요한지 살펴봅니다.

비교하지 않고 나누어 담기

시험 점수처럼 값이 0부터 5까지의 정수뿐이라면, 0부터 5까지 이름표를 붙인 상자 여섯 개를 준비하고 각 값을 자기 이름표의 상자에 넣은 뒤, 0번 상자부터 차례로 꺼내 이으면 정렬이 끝납니다. 값끼리 한 번도 비교하지 않았는데도 말입니다. 이렇게 값을 담는 상자를 버킷(bucket)이라 하고, 값의 범위만큼 버킷을 두고 나누어 담는 정렬을 계수 정렬(counting sort)이라고 합니다. 원래는 버킷마다 값의 개수만 세는 방법이라 이런 이름이 붙었고, 여기서는 값을 그대로 담는 형태로 씁니다.

def counting_sort(scores, highest):
    buckets = [[] for _ in range(highest + 1)]
    for score in scores:
        buckets[score].append(score)
    return [score for bucket in buckets for score in bucket]


print(counting_sort([3, 1, 4, 1, 5, 2, 0], 5))

[0, 1, 1, 2, 3, 4, 5]

마지막 줄의 리스트 컴프리헨션은 버킷을 0번부터 차례로 보며 그 안의 값을 모두 꺼내 하나의 리스트로 잇습니다. 값 n개를 한 번씩 담고 버킷 k개를 한 번씩 보므로 비용은 O(n + k)입니다. 값의 범위 k가 n보다 작거나 비슷하면 아주 빠르지만, 값이 0부터 10억까지라면 버킷이 10억 개 필요해서 쓸 수 없습니다.

자리별로 나누어 담기

값의 범위가 넓을 때는 값 전체가 아니라 한 자리씩 나누어 담습니다. 10진수의 각 자리는 0부터 9까지이므로, 버킷 10개로 한 자리를 처리할 수 있습니다. 수 value의 일의 자리는 value % 10, 십의 자리는 (value // 10) % 10이고, 일반적으로 자리의 크기 place가 1, 10, 100, …일 때 그 자리 숫자는 (value // place) % 10입니다. 수의 표현에서 자리마다 쓰는 숫자의 개수, 곧 10진수의 10을 밑 또는 기수(radix)라고 하며, 자리별로 나누어 담는 정렬을 기수 정렬(radix sort)이라고 합니다.

기수 정렬은 가장 낮은 자리부터 시작합니다. 일의 자리로 버킷에 나누어 담고 0번 버킷부터 차례로 꺼내 이은 다음, 그 결과를 십의 자리로 다시 나누어 담고 꺼내기를 가장 높은 자리까지 되풀이합니다. 낮은 자리(least significant digit)부터 처리한다고 해서 LSD 기수 정렬이라고 부릅니다. 자릿수가 적은 수는 없는 높은 자리를 0으로 봅니다. [21, 13, 12, 3]을 정렬하는 과정은 다음과 같습니다.

십의 자리 단계에서 12와 13은 같은 1번 버킷에 들어갑니다. 이 둘의 순서는 십의 자리만으로는 정할 수 없는데, 버킷에 들어간 순서대로 꺼냈더니 일의 자리 단계에서 만든 12, 13의 순서가 그대로 남아 올바른 결과가 되었습니다. 이것이 기수 정렬이 맞는 이유의 핵심입니다.

def radix_sort(values, base=10, show=False):
    if any(type(value) is not int or value < 0 for value in values):
        raise ValueError("0 이상인 정수만 정렬할 수 있습니다")
    result = list(values)
    place, largest, passes = 1, max(result, default=0), 0
    while largest // place > 0:
        buckets = [[] for _ in range(base)]
        for value in result:
            buckets[(value // place) % base].append(value)
        result = [value for bucket in buckets for value in bucket]
        passes += 1
        if show:
            print("자리", place, result)
        place *= base
    return result, passes


print(radix_sort([21, 13, 12, 3], show=True))
print(radix_sort([0, 10, 0, 1])[0], radix_sort([])[0])
try:
    radix_sort([-1, 2])
except ValueError as error:
    print("오류:", error)

자리 1 [21, 12, 13, 3]
자리 10 [3, 12, 13, 21]
([3, 12, 13, 21], 2)
[0, 0, 1, 10] []
오류: 0 이상인 정수만 정렬할 수 있습니다

반복은 가장 큰 값을 place로 나눈 몫이 0이 되면, 곧 가장 큰 값의 모든 자리를 처리하면 멈춥니다. 함수는 정렬 결과와 함께 자리를 처리한 횟수 passes를 돌려줍니다. max(result, default=0)은 빈 리스트일 때 0을 쓰라는 뜻이라서, 빈 리스트는 한 번도 반복하지 않고 그대로 돌아옵니다. 음수나 실수는 이 방법으로 자리를 뽑을 수 없으므로 처음에 거절합니다.

왜 낮은 자리부터, 왜 순서를 지켜야 하나

k번째 자리까지 처리한 뒤에는, 리스트가 각 수의 낮은 k자리만 본 값의 순서로 정렬되어 있습니다. 일의 자리 단계가 끝나면 일의 자리 순서로, 십의 자리 단계가 끝나면 끝 두 자리 순서로 정렬되는 식입니다. 다음 자리로 나누어 담을 때 그 자리 숫자가 다른 두 수는 버킷의 순서로 바르게 놓이고, 그 자리 숫자가 같은 두 수는 같은 버킷에 들어가 들어간 순서대로 나오므로 낮은 자리들의 순서가 유지됩니다. 그래서 가장 높은 자리까지 처리하면 수 전체의 순서로 정렬됩니다.

이 설명에서 두 가지가 꼭 필요합니다. 하나는 같은 버킷에 들어간 값들을 들어간 순서대로 꺼내는 것, 곧 각 단계가 안정 정렬이어야 한다는 것입니다. 버킷 안의 순서를 뒤집으면 [12, 13]은 십의 자리 단계에서 같은 1번 버킷에 12, 13 순서로 들어갔다가 13, 12 순서로 나와 틀린 결과가 됩니다. 다른 하나는 낮은 자리부터 처리하는 것입니다. 높은 자리부터 처리하면 마지막으로 처리한 일의 자리가 결과의 순서를 정해 버려서, [21, 13, 12, 3]이 일의 자리 순서인 [21, 12, 3, 13]으로 끝납니다. 가장 나중에 처리하는 자리가 가장 강하게 순서를 정하므로, 가장 중요한 자리인 가장 높은 자리를 마지막에 처리해야 합니다.

비용과 밑의 선택

가장 큰 값의 자릿수가 d이고 밑이 b이면, 자리마다 값 n개를 나누어 담고 버킷 b개를 훑으므로 전체 비용은 O(d(n + b))입니다. 공간은 버킷과 결과를 합해 O(n + b)입니다. d와 b가 n에 비해 작은 상수라면 O(n)에 가깝지만, 값이 클수록 d가 커지므로 "기수 정렬은 늘 O(n)"이라고 말할 수는 없습니다. 비교 정렬의 하한과 충돌하지 않는 것은, 기수 정렬이 값을 비교하는 대신 정수의 자릿수라는 추가 정보를 쓰기 때문입니다.

밑을 크게 하면 자릿수 d가 줄어듭니다. 10억보다 작은 수는 10진수로 9자리이지만 256진수로는 4자리이므로, 밑을 256으로 바꾸면 처리 횟수가 9번에서 4번으로 줄어듭니다. 대신 버킷이 256개로 늘어나므로, n이 매우 작을 때는 오히려 손해일 수 있습니다. 컴퓨터는 수를 이진수로 저장하므로, 실제 구현에서는 256처럼 2의 거듭제곱을 밑으로 써서 나눗셈 대신 비트 연산으로 자리를 뽑습니다.

import random


def radix_sort(values, base=10):
    result = list(values)
    place, largest, passes = 1, max(result, default=0), 0
    while largest // place > 0:
        buckets = [[] for _ in range(base)]
        for value in result:
            buckets[(value // place) % base].append(value)
        result = [value for bucket in buckets for value in bucket]
        passes += 1
        place *= base
    return result, passes


rng = random.Random(2026)
values = [rng.randrange(10**9) for _ in range(1000)]
for base in [10, 256]:
    result, passes = radix_sort(values, base)
    print(base, result == sorted(values), passes)

10 True 9
256 True 4

음수가 섞여 있다면 가장 작은 값을 모든 값에서 빼서 0 이상으로 만든 뒤 정렬하고, 다시 더해 원래 값으로 되돌리면 됩니다. 문자열도 글자의 코드를 자리로 보면 같은 방식으로 정렬할 수 있지만, 길이가 다른 문자열을 어떻게 맞출지, 언어의 사전 순서를 어떻게 따를지를 따로 정해야 하므로 이 글의 코드를 그대로 쓸 수는 없습니다.

정리

• 값이 작은 범위의 정수라면 값마다 버킷을 두고 나누어 담는 계수 정렬로 O(n + k)에 정렬할 수 있습니다.
• LSD 기수 정렬은 가장 낮은 자리부터 가장 높은 자리까지, 자리마다 버킷에 나누어 담고 차례로 꺼내 이어 정렬합니다.
• k번째 자리까지 처리하면 낮은 k자리의 순서로 정렬되므로, 가장 높은 자리까지 처리하면 전체가 정렬됩니다.
• 각 단계는 같은 버킷의 순서를 지키는 안정 정렬이어야 하고, 가장 중요한 높은 자리를 마지막에 처리해야 합니다.
• 비용은 O(d(n + b))이며, 밑 b를 키우면 자릿수 d가 줄지만 버킷이 늘어납니다. 값끼리 비교하지 않으므로 비교 정렬의 하한에 묶이지 않습니다.

연습 문제

1. 일의 자리 단계

[32, 21, 12]를 기수 정렬할 때 일의 자리 단계가 끝난 뒤의 리스트를 쓰세요.

2. 버킷 안의 순서를 뒤집으면

버킷에서 값을 꺼낼 때 들어간 순서와 반대로 꺼내면 [12, 13]의 결과는 어떻게 될까요?

3. 밑에 따른 처리 횟수

0부터 99999까지의 정수를 기수 정렬할 때, 밑이 10이면 자리를 몇 번 처리하고, 밑이 100이면 몇 번 처리하나요?

다음 글 선택 심화: 런·다중 병합·외부 정렬에서는 값의 성질 대신 메모리의 크기가 제약이 되는 경우, 곧 메모리에 다 들어가지 않는 자료를 정렬하는 방법을 다룹니다.