선택 심화: Shell 정렬과 간격

이 장은 핵심 과정을 마친 뒤 골라 읽는 선택 심화입니다. 첫 글에서는 삽입 정렬을 조금 바꾸어 훨씬 빠르게 만드는 Shell 정렬을 다룹니다. 삽입 정렬은 거의 정렬된 입력에서는 매우 빠르지만, 값이 제자리에서 멀리 떨어져 있으면 한 칸씩 밀어 옮기느라 느려졌습니다. 맨 끝에 있는 가장 작은 값을 맨 앞으로 보내려면 n - 1번을 밀어야 하는 것입니다. 1959년 Donald Shell은 처음에는 멀리 떨어진 칸끼리 비교하며 값을 크게 옮기고, 그 간격을 점점 줄여 마지막에 보통의 삽입 정렬로 마무리하는 방법을 제안했습니다. 이 글에서는 Shell 정렬을 만들고, 간격을 어떻게 고르느냐에 따라 성능이 크게 달라지는 것을 확인합니다.

간격을 두고 삽입 정렬하기

간격 gap을 정하면, 인덱스를 gap으로 나눈 나머지가 같은 칸들이 하나의 묶음이 됩니다. gap이 3이면 인덱스 0, 3, 6, …이 한 묶음, 1, 4, 7, …이 한 묶음, 2, 5, 8, …이 한 묶음입니다. Shell 정렬은 이 묶음마다 따로 삽입 정렬을 합니다. 묶음 안에서 바로 옆 값은 리스트에서 gap만큼 떨어져 있으므로, 값을 한 번 밀 때 gap칸을 한꺼번에 옮기게 됩니다.

[8, 5, 3, 1, 6, 2]를 gap 3으로 정렬하면 다음과 같습니다.

세 묶음을 정렬하면 리스트는 [1, 5, 2, 8, 6, 3]이 됩니다. 아직 정렬되지는 않았지만, 맨 앞에 있던 8이 한 번에 세 칸 뒤로 가고 맨 뒤 근처의 1이 맨 앞으로 오는 등 큰 이동이 이미 끝났습니다. 그다음 gap을 1로 줄이면 묶음이 리스트 전체 하나가 되어 보통의 삽입 정렬이 되는데, 이때는 값들이 이미 제자리 가까이 있어서 밀어야 할 거리가 짧습니다.

코드로 옮기기

아래 코드는 gap을 n // 2에서 시작해 절반씩 줄입니다. 묶음을 새 리스트로 잘라 내지 않고, 원래 리스트에서 gap만큼 떨어진 칸들끼리 비교하고 옮깁니다. 삽입 정렬의 코드에서 1이던 자리를 gap으로 바꾸기만 하면 됩니다. 이 함수는 미는 횟수도 세어 돌려주고, show=True이면 gap마다 리스트를 출력합니다.

def shell_sort(values, gaps=None, show=False):
    result = list(values)
    if gaps is None:
        gaps = []
        gap = len(result) // 2
        while gap > 0:
            gaps.append(gap)
            gap //= 2
    shifts = 0
    for gap in gaps:
        for i in range(gap, len(result)):
            current, j = result[i], i
            while j >= gap and result[j - gap] > current:
                result[j] = result[j - gap]
                j -= gap
                shifts += 1
            result[j] = current
        if show:
            print("간격", gap, result)
    return result, shifts


print(shell_sort([8, 5, 3, 1, 6, 2], show=True))
print(shell_sort([2, 2, 1])[0], shell_sort([])[0])

간격 3 [1, 5, 2, 8, 6, 3]
간격 1 [1, 2, 3, 5, 6, 8]
([1, 2, 3, 5, 6, 8], 7)
[1, 2, 2] []

for i in range(gap, len(result))는 인덱스 gap부터 끝까지 차례로 보면서, 각 칸을 자기 묶음의 앞부분에 끼워 넣습니다. 묶음을 하나씩 따로 정렬하지 않고 여러 묶음을 번갈아 조금씩 정렬하는 셈이지만, 각 묶음 안에서 보면 삽입 정렬과 똑같은 일을 합니다. 길이 6이면 gap은 3, 1의 순서입니다.

왜 맞는가

Shell 정렬이 늘 정렬된 결과를 내는 이유는 간단합니다. 길이가 0이나 1인 리스트는 gap이 하나도 없지만 처음부터 정렬되어 있습니다. 그보다 긴 리스트에서는 마지막 gap이 늘 1이고, gap 1일 때의 작업은 리스트 전체에 대한 보통의 삽입 정렬이기 때문입니다. 삽입 정렬은 입력이 어떻든 정렬된 결과를 내므로, 그 전의 gap들이 리스트를 어떻게 바꾸어 놓았든 마지막 결과는 정렬되어 있습니다. 앞의 gap들은 값을 서로 옮기기만 하므로 값의 종류와 개수도 그대로입니다.

그러니 앞의 gap들은 정확성이 아니라 속도를 위한 것입니다. 큰 gap에서 값들을 제자리 가까이 옮겨 역순 쌍을 미리 많이 없애 두면, 마지막 삽입 정렬이 밀어야 할 횟수가 크게 줄어듭니다. 또 어떤 gap으로 정렬해 둔 성질은 더 작은 gap으로 정렬한 뒤에도 깨지지 않는다는 것이 알려져 있어서, 앞에서 한 일이 뒤에서 헛되이 되돌려지지 않습니다. gap은 절반씩 줄어 결국 0이 되므로 반복도 끝납니다.

간격 수열이 성능을 정한다

어떤 gap들을 어떤 순서로 쓸지를 간격 수열(gap sequence)이라고 합니다. 이 글의 절반씩 줄이는 수열은 Shell이 처음 제안한 것이지만, 가장 좋은 수열은 아닙니다. Donald Knuth가 제안한 1, 4, 13, 40, 121, …처럼 앞의 수에 3을 곱하고 1을 더해 만드는 수열과 비교해 보겠습니다. 아래 코드는 무작위 입력 1000개와, 짝수 칸에 큰 값을, 홀수 칸에 작은 값을 둔 길이 1024의 입력에서 미는 횟수를 셉니다.

import random


def shell_sort(values, gaps):
    result = list(values)
    shifts = 0
    for gap in gaps:
        for i in range(gap, len(result)):
            current, j = result[i], i
            while j >= gap and result[j - gap] > current:
                result[j] = result[j - gap]
                j -= gap
                shifts += 1
            result[j] = current
    return result, shifts


def halving_gaps(n):
    gaps, gap = [], n // 2
    while gap > 0:
        gaps.append(gap)
        gap //= 2
    return gaps


def knuth_gaps(n):
    gaps, h = [], 1
    while h < n:
        gaps.append(h)
        h = 3 * h + 1
    return gaps[::-1] or [1]


rng = random.Random(2026)
random_values = [rng.randrange(1_000_000) for _ in range(1000)]
n = 1024
bad = [0] * n
bad[0::2] = range(n // 2 + 1, n + 1)
bad[1::2] = range(1, n // 2 + 1)
for name, values in [("무작위 1000개", random_values), ("나쁜 입력 1024개", bad)]:
    insertion = shell_sort(values, [1])[1]
    halving = shell_sort(values, halving_gaps(len(values)))[1]
    knuth = shell_sort(values, knuth_gaps(len(values)))[1]
    print(name, "삽입", insertion, "절반", halving, "Knuth", knuth)

무작위 1000개 삽입 258583 절반 7691 Knuth 9239
나쁜 입력 1024개 삽입 131328 절반 131328 Knuth 3920

bad[0::2]는 인덱스 0부터 두 칸 간격의 칸들, 곧 짝수 칸에 513부터 1024까지를 넣고, bad[1::2]는 홀수 칸에 1부터 512까지를 넣습니다. 무작위 입력에서는 두 간격 수열 모두 삽입 정렬의 25만 번을 1만 번 아래로 줄였습니다. 그런데 나쁜 입력에서 절반 수열은 삽입 정렬과 미는 횟수가 똑같습니다. 길이가 1024이면 gap이 512, 256, …, 2로 모두 짝수라서, 짝수 칸은 짝수 칸끼리, 홀수 칸은 홀수 칸끼리만 비교됩니다. 이 입력은 짝수 칸끼리, 홀수 칸끼리는 이미 정렬되어 있으므로 앞의 gap들이 아무것도 바꾸지 못하고, 마지막 gap 1에서 작은 값들을 모두 멀리 옮겨야 합니다. Knuth 수열은 홀수와 짝수가 섞여 있어 이 입력을 3920번 만에 정렬합니다.

이처럼 간격 수열에 따라 성능이 크게 달라지므로, Shell 정렬에는 하나의 시간 복잡도를 붙일 수 없습니다. 절반 수열은 위의 예처럼 최악의 경우 Θ(n²)이고, Knuth 수열은 최악의 경우 n의 1.5제곱에 비례하는 것으로 알려져 있습니다. 더 좋은 수열을 찾는 연구가 지금도 이어지고 있으며, 실험으로 찾은 1, 4, 10, 23, 57, 132, 301, 701 같은 Ciura의 수열이 실제로 잘 동작하는 것으로 알려져 있습니다.

비용과 쓰임

Shell 정렬은 리스트 안에서 값을 옮기기만 하므로 변수 몇 개 외의 추가 공간이 들지 않고, 이 글의 함수는 원본을 남기려는 복사 때문에 O(n)을 더 씁니다. 같은 키의 순서는 지키지 않습니다. gap만큼 떨어진 값을 옮길 때 사이에 있는 같은 키의 값을 건너뛸 수 있기 때문입니다. 예를 들어 [(2, "가"), (2, "나"), (1, "다"), (3, "라")]를 첫 값으로 정렬하면 결과는 [(1, '다'), (2, '나'), (2, '가'), (3, '라')]가 되어 "가"와 "나"의 순서가 뒤집힙니다.

코드가 짧고 추가 공간이 필요 없으면서, 원소가 수천 개 정도인 입력에서는 꽤 빠르다는 것이 Shell 정렬의 장점입니다. 그래서 메모리가 작은 장치처럼 복잡한 정렬을 넣기 부담스러운 곳에서 쓰입니다. 하지만 최악의 경우를 확실히 보장해야 하거나 입력이 매우 크다면 병합 정렬이나 힙 정렬처럼 O(n log n)이 보장되는 정렬이 낫습니다.

정리

• Shell 정렬은 간격 gap만큼 떨어진 칸들의 묶음마다 삽입 정렬을 하며, gap을 줄여 가다 마지막에 gap 1로 전체를 삽입 정렬합니다.
• 마지막 gap 1이 보통의 삽입 정렬이므로 결과는 늘 정렬되어 있고, 앞의 gap들은 값을 멀리 옮겨 역순 쌍을 미리 줄이는 속도의 역할을 합니다.
• 간격 수열에 따라 성능이 크게 달라집니다. 절반씩 줄이는 수열은 gap이 모두 짝수가 되는 입력에서 삽입 정렬만큼 느려질 수 있습니다.
• Knuth 수열처럼 더 나은 수열을 쓰면 최악의 경우도 크게 줄지만, Shell 정렬 전체에 하나의 시간 복잡도를 붙일 수는 없습니다.
• 추가 공간이 거의 들지 않지만 안정 정렬은 아닙니다.

연습 문제

1. 간격의 순서

길이가 8인 리스트를 본문의 shell_sort로 정렬할 때 쓰는 gap을 순서대로 쓰세요. 길이가 7이면 어떻게 될까요?

2. 마지막 gap 1을 빼면

gap 2까지만 정렬하고 gap 1을 건너뛰어도 리스트가 정렬될까요? [1, 4, 2, 5, 3, 6]으로 생각해 보세요.

3. 같은 키의 순서

본문의 비용과 쓰임에서 본 예처럼 Shell 정렬은 같은 키의 순서를 뒤집을 수 있습니다. 같은 일이 보통의 삽입 정렬, 곧 gap이 처음부터 1인 경우에도 일어날까요?

다음 글 선택 심화: 자릿수·버킷·기수 정렬에서는 값끼리 비교하지 않고 값의 자릿수를 이용해 정렬하는 방법을 봅니다.