퀵 정렬·피벗·세 갈래 분할

병합 정렬은 리스트를 아무렇게나 반으로 나누고, 정렬된 두 반쪽을 합치는 데 공을 들였습니다. 퀵 정렬(quick sort)은 반대로 나누는 데 공을 들입니다. 기준이 되는 값을 하나 골라 그보다 작은 값과 큰 값으로 먼저 나누어 두면, 각 무리를 따로 정렬한 뒤 이어 붙이기만 해도 전체가 정렬됩니다. 1959년 무렵 Tony Hoare가 고안한 이 방법은 평균적으로 매우 빨라서 오늘날에도 여러 언어의 정렬 라이브러리에 쓰입니다. 이 글에서는 퀵 정렬을 만들고, 기준값을 어떻게 고르느냐에 따라 비용이 O(n log n)에서 O(n²)까지 달라지는 이유를 실험으로 확인합니다.

피벗을 기준으로 세 무리로 나누기

나누는 기준으로 고른 값을 피벗(pivot)이라고 합니다. 리스트의 모든 값을 피벗과 비교해 피벗보다 작은 값, 피벗과 같은 값, 피벗보다 큰 값의 세 무리로 나누는 일을 분할(partition)이라고 합니다. 분할이 끝나면 작은 무리의 어떤 값도 같은 무리의 값보다 작고, 같은 무리의 값은 큰 무리의 어떤 값보다도 작습니다. 그래서 작은 무리와 큰 무리를 각각 정렬해 작은 무리, 같은 무리, 큰 무리 순서로 이어 붙이면 병합 없이도 전체가 정렬됩니다.

[4, 2, 3, 1, 3]에서 가운데 위치의 값 3을 피벗으로 골라 분할해 보겠습니다.

분할 결과는 작은 무리 [2, 1], 같은 무리 [3, 3], 큰 무리 [4]입니다. 작은 무리 [2, 1]은 다시 가운데 위치의 값 1을 피벗으로 나누어 [], [1], [2]가 되고, 이어 붙이면 [1, 2]입니다. 원소가 하나인 큰 무리 [4]는 이미 정렬되어 있습니다. 마지막으로 [1, 2], [3, 3], [4]를 이어 붙이면 [1, 2, 3, 3, 4]가 됩니다.

코드에서는 함수·리스트·복사와 작은 검사에서 본 리스트 컴프리헨션으로 세 무리를 만듭니다. [x for x in values if x < pivot]은 values에서 피벗보다 작은 값만 골라 담은 새 리스트입니다. 작은 무리, 같은 무리, 큰 무리는 코드에서 각각 less, equal, greater이며, 앞의 단계 도표에서 lower라고 적은 무리가 코드의 less입니다.

def quick_sort(values):
    if len(values) <= 1:
        return list(values)
    pivot = values[len(values) // 2]
    less = [x for x in values if x < pivot]
    equal = [x for x in values if x == pivot]
    greater = [x for x in values if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)


print(quick_sort([4, 2, 3, 1, 3]))
print(quick_sort([2, 2, 2]))
print(quick_sort([]))

[1, 2, 3, 3, 4]
[2, 2, 2]
[]

이 구현은 세 무리를 만들려고 리스트를 세 번 훑습니다. 한 번에 훑으며 세 무리로 나누면 비교가 줄지만, 비용의 증가율은 같으므로 여기서는 읽기 쉬운 쪽을 택했습니다.

왜 맞고 왜 끝나는가

정확성은 귀납법으로 설명합니다. 원소가 하나 이하인 리스트는 그대로 돌려주면 맞습니다. 그보다 긴 리스트에서 모든 값은 피벗보다 작거나, 같거나, 크거나 셋 중 정확히 하나이므로 세 무리 중 정확히 한 곳에 들어가고, 값을 잃거나 두 번 넣는 일이 없습니다. 작은 무리와 큰 무리가 재귀 호출로 바르게 정렬된다고 가정하면, 앞에서 본 이유로 세 무리를 이어 붙인 결과도 정렬되어 있습니다.

끝난다는 것은 무리의 길이로 보입니다. 피벗은 리스트 안의 값이므로 같은 무리에는 적어도 피벗 자신이 들어갑니다. 그래서 작은 무리와 큰 무리는 원래 리스트보다 적어도 하나 짧고, 재귀 호출마다 길이가 줄어 결국 기저 사례에 도착합니다.

같은 값을 따로 모으는 이유

같은 무리를 따로 두지 않고, 피벗보다 작은 값과 피벗 이상인 값의 두 무리로만 나누면 어떻게 될까요? 아래 quick_sort_two_way는 앞 코드에서 equal을 없애고, 피벗과 같은 값을 x >= pivot인 rest에 함께 넣습니다. 피벗을 고르는 방법과 기저 사례는 그대로이므로, 달라진 것은 피벗 자신이 어느 무리로 가느냐뿐입니다.

def quick_sort_two_way(values):
    if len(values) <= 1:
        return list(values)
    pivot = values[len(values) // 2]
    less = [x for x in values if x < pivot]
    rest = [x for x in values if x >= pivot]
    return quick_sort_two_way(less) + quick_sort_two_way(rest)


print(quick_sort_two_way([3, 1, 2]))

Traceback (most recent call last):
  File "C:\algo\lesson.py", line 10, in <module>
    print(quick_sort_two_way([3, 1, 2]))
          ~~~~~~~~~~~~~~~~~~^^^^^^^^^^^
  File "C:\algo\lesson.py", line 7, in quick_sort_two_way
    return quick_sort_two_way(less) + quick_sort_two_way(rest)
                                      ~~~~~~~~~~~~~~~~~~^^^^^^
  File "C:\algo\lesson.py", line 7, in quick_sort_two_way
    return quick_sort_two_way(less) + quick_sort_two_way(rest)
                                      ~~~~~~~~~~~~~~~~~~^^^^^^
  File "C:\algo\lesson.py", line 7, in quick_sort_two_way
    return quick_sort_two_way(less) + quick_sort_two_way(rest)
                                      ~~~~~~~~~~~~~~~~~~^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

[3, 1, 2]의 가운데 값 1은 이 리스트의 최솟값입니다. 그러면 less는 비고 rest는 [3, 1, 2] 전체가 되어, 처음과 똑같은 호출이 끝없이 되풀이됩니다. 피벗이 rest 쪽에 남아 길이가 줄지 않기 때문입니다. 같은 무리를 따로 두면 피벗이 반드시 재귀 호출에서 빠지므로 이런 일이 생기지 않습니다. 또 [7, 7, 7, 7]처럼 같은 값이 많은 입력에서는 한 번의 분할로 모든 값이 같은 무리에 들어가 바로 끝납니다. 같은 값을 따로 모으는 이 방법을 세 갈래 분할(three-way partition)이라고 합니다.

피벗이 분할의 균형을 정한다

퀵 정렬의 비용은 분할이 얼마나 고르게 되느냐에 달려 있습니다. 한 번의 분할은 리스트의 모든 값을 피벗과 비교하므로 길이에 비례하는 비용이 듭니다. 피벗이 늘 값들의 중앙값 근처라서 두 무리가 거의 같은 크기로 나뉜다면, 병합 정렬처럼 약 log₂ n층의 재귀가 생기고 층마다 O(n)의 분할 비용이 들어 전체가 O(n log n)입니다. 반대로 피벗이 늘 최솟값이나 최댓값이라면 한쪽 무리는 비고 다른 쪽에 나머지가 모두 몰려, 길이가 n, n - 1, n - 2, …인 분할을 차례로 하게 됩니다. 그러면 비용이 n + (n - 1) + … + 2, 곧 약 n²/2로 O(n²)이 됩니다.

아래 코드는 분할할 때 살펴본 원소 수와 재귀의 깊이를 세면서, 피벗을 고르는 방법과 입력을 바꾸어 비교합니다. choose_pivot은 피벗을 고르는 함수를 받는 매개변수입니다. middle_killer(n)은 가운데 위치의 값이 매번 남은 값 중 최솟값이 되도록 일부러 만든 입력입니다. 가장 큰 값 하나에서 시작해, 새로 넣는 가장 작은 값이 늘 가운데 위치에 오도록 하나씩 끼워 넣어 만듭니다.

import random


def quick_sort_count(values, choose_pivot, stats, depth=1):
    stats["depth"] = max(stats["depth"], depth)
    if len(values) <= 1:
        return list(values)
    stats["scanned"] += len(values)
    pivot = choose_pivot(values)
    less = [x for x in values if x < pivot]
    equal = [x for x in values if x == pivot]
    greater = [x for x in values if x > pivot]
    left = quick_sort_count(less, choose_pivot, stats, depth + 1)
    right = quick_sort_count(greater, choose_pivot, stats, depth + 1)
    return left + equal + right


def middle_pivot(values):
    return values[len(values) // 2]


rng = random.Random(2026)


def random_pivot(values):
    return rng.choice(values)


def middle_killer(n):
    values = [n]
    for k in range(2, n + 1):
        values.insert(k // 2, n - k + 1)
    return values


cases = [
    ("무작위 입력, 가운데 피벗", rng.sample(range(1, 501), 500), middle_pivot),
    ("정렬된 입력, 가운데 피벗", list(range(1, 501)), middle_pivot),
    ("나쁜 입력, 가운데 피벗", middle_killer(500), middle_pivot),
    ("나쁜 입력, 무작위 피벗", middle_killer(500), random_pivot),
]
print(middle_killer(5))
for name, values, choose_pivot in cases:
    stats = {"scanned": 0, "depth": 0}
    assert quick_sort_count(values, choose_pivot, stats) == sorted(values)
    print(f"{name}: 살펴본 원소 {stats['scanned']}, 깊이 {stats['depth']}")

[5, 3, 1, 2, 4]
무작위 입력, 가운데 피벗: 살펴본 원소 5261, 깊이 22
정렬된 입력, 가운데 피벗: 살펴본 원소 3753, 깊이 9
나쁜 입력, 가운데 피벗: 살펴본 원소 125249, 깊이 500
나쁜 입력, 무작위 피벗: 살펴본 원소 5136, 깊이 20

rng.sample(range(1, 501), 500)은 1부터 500까지의 수를 무작위 순서로 늘어놓은 리스트이고, rng.choice(values)는 values에서 값 하나를 무작위로 고릅니다. 첫 줄의 [5, 3, 1, 2, 4]는 나쁜 입력의 작은 예입니다. 가운데 값 1을 피벗으로 쓰면 큰 무리 [5, 3, 2, 4]가 남고, 그 가운데 값은 다시 최솟값 2가 됩니다.

원소 500개에서 n log₂ n은 약 4500입니다. 무작위 입력은 5261개를 살펴보아 이 규모에 가깝고, 정렬된 입력은 가운데 위치의 값이 마침 중앙값이라 분할이 완벽하게 고르게 되어 깊이가 9에 그쳤습니다. 나쁜 입력에서는 피벗이 매번 최솟값이라 깊이가 원소 수와 같은 500이 되었고, 살펴본 원소도 2 + 3 + … + 500 = 125249개로 n²/2 규모입니다. 같은 퀵 정렬이 입력에 따라 약 24배 느려진 것입니다.

피벗을 무작위로 고르기

가운데 위치든 첫 위치든, 피벗을 정해진 규칙으로 고르면 그 규칙을 피하는 나쁜 입력을 만들 수 있습니다. 위의 middle_killer가 그런 예입니다. 이 문제를 피하는 간단한 방법은 피벗을 무작위로 고르는 것입니다. 마지막 줄처럼 같은 나쁜 입력에서도 무작위 피벗은 5136개만 살펴보고 깊이 20으로 끝났습니다.

무작위 피벗이 좋은 이유는 입력이 무엇이든 피벗이 지나치게 한쪽으로 치우칠 확률이 낮다는 데 있습니다. 피벗이 값들의 순위에서 가운데 절반 안에 들 확률은 매번 1/2이고, 그렇게 고른 피벗은 큰 쪽 무리를 원래 길이의 3/4 이하로 줄입니다. 이런 좋은 분할이 충분히 자주 일어나므로, 값을 한 번씩 훑는 분할을 기준으로 할 때, 무작위 피벗을 쓰는 퀵 정렬의 비교 횟수는 어떤 입력에서든 평균이 약 1.39 n log₂ n이라는 것이 알려져 있습니다. 운이 매우 나쁘면 여전히 O(n²)이 될 수 있지만, n이 클 때 그럴 확률은 무시해도 될 만큼 작습니다.

비용과 쓰임

퀵 정렬은 분할이 고르면 O(n log n), 계속 한쪽으로 치우치면 O(n²)이고, 무작위 피벗을 쓰면 어떤 입력에서든 평균 O(n log n)입니다. 이 글의 구현은 분할할 때마다 새 리스트를 만들므로 공간도 따져야 합니다. 고르게 나뉠 때는 동시에 살아 있는 리스트가 O(n) 규모이지만, 나쁜 입력에서는 깊이가 n이 되고 각 층의 리스트가 모두 살아 있어 O(n²)까지 쓸 수 있습니다. 깊이가 n이 되므로 원소가 1000개쯤 되는 입력에서는 RecursionError도 납니다.

같은 키의 순서를 보면, 이 글의 구현은 원래 순서대로 훑으면서 무리를 만들고 같은 무리를 그대로 이어 붙이므로 안정 정렬입니다. 하지만 실제로 쓰이는 퀵 정렬은 대부분 아래의 더 깊이에서 볼 제자리 분할을 쓰며, 멀리 떨어진 값을 맞바꾸기 때문에 안정 정렬이 아닙니다. 또 실제 구현은 최악의 경우를 막으려고 재귀가 너무 깊어지면 힙 정렬로 바꾸기도 합니다. 이런 방법을 introsort라 하며, C++ 표준 라이브러리의 여러 구현이 std::sort에 씁니다.

더 깊이: 리스트를 새로 만들지 않는 제자리 분할

퀵 정렬이 실제로 빠른 이유 가운데 하나는 추가 리스트 없이 입력 리스트 안에서 값을 맞바꾸며 분할할 수 있다는 점입니다. 아래의 partition은 [lo, hi) 구간의 마지막 값을 피벗으로 삼아, 피벗보다 작은 값을 구간 앞쪽으로 모읍니다. 반복하는 동안 values[lo:i]에는 피벗보다 작은 값이, values[i:j]에는 피벗 이상인 값이 들어 있습니다. j번 값이 피벗보다 작으면 i번 값과 맞바꾸고 i를 한 칸 늘려 이 사실을 유지합니다. 반복이 끝나면 피벗을 i번 칸과 맞바꾸어, 피벗보다 작은 값들과 그 이상인 값들 사이에 놓습니다.

def partition(values, lo, hi):
    pivot = values[hi - 1]
    i = lo
    for j in range(lo, hi - 1):
        if values[j] < pivot:
            values[i], values[j] = values[j], values[i]
            i += 1
    values[i], values[hi - 1] = values[hi - 1], values[i]
    return i


def quick_sort_in_place(values, lo=0, hi=None):
    if hi is None:
        hi = len(values)
    if hi - lo > 1:
        p = partition(values, lo, hi)
        quick_sort_in_place(values, lo, p)
        quick_sort_in_place(values, p + 1, hi)


sample = [4, 2, 5, 1, 3]
print(partition(sample, 0, 5), sample)
values = [4, 2, 3, 1, 3]
quick_sort_in_place(values)
print(values)

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

[4, 2, 5, 1, 3]에서 피벗은 마지막 값 3입니다. 2와 1이 피벗보다 작아 앞쪽 두 칸으로 모이고, 피벗 3이 2번 칸에 놓여 [2, 1, 3, 4, 5]가 됩니다. 이제 피벗의 자리는 확정되었으므로 그 왼쪽 [0, 2)와 오른쪽 [3, 5)만 각각 정렬하면 됩니다. 이 방법은 새 리스트를 만들지 않아 고르게 나뉠 때 재귀 깊이만큼인 O(log n)의 공간만 씁니다.

다만 이 분할은 세 갈래가 아니라서, 같은 값이 많은 입력에서는 다시 느려집니다. 모든 값이 같으면 피벗보다 작은 값이 하나도 없어 피벗이 매번 구간의 맨 앞에 놓이고, 한쪽 구간만 하나씩 줄어 O(n²)이 됩니다. 실제 구현은 Dijkstra가 제안한 방법처럼 제자리에서 세 갈래로 나누는 분할을 써서 이 문제를 피합니다.

정리

• 퀵 정렬은 피벗을 기준으로 값을 작은 무리, 같은 무리, 큰 무리로 나누고, 작은 무리와 큰 무리만 재귀로 정렬해 이어 붙입니다. 병합 단계가 필요 없습니다.
• 같은 무리에 피벗이 반드시 들어가므로 재귀 호출의 길이가 줄어 끝납니다. 두 무리로만 나누면 피벗이 최솟값일 때 같은 호출이 끝없이 되풀이될 수 있습니다.
• 분할이 고르면 O(n log n), 피벗이 계속 최솟값이나 최댓값이면 O(n²)입니다. 정해진 규칙의 피벗에는 그 규칙을 피하는 나쁜 입력이 있습니다.
• 피벗을 무작위로 고르면 어떤 입력에서든 평균 O(n log n)이고, 나쁜 분할이 계속될 확률은 매우 작습니다.
• 실제 구현은 제자리 분할로 추가 공간을 줄이며, 이때는 안정 정렬이 아닙니다.

연습 문제

1. 모든 값이 같을 때

quick_sort([7, 7, 7, 7, 7])은 재귀 호출을 몇 번 하고, 분할에서 몇 개의 원소를 살펴볼까요?

2. 가운데 위치가 늘 좋은 피벗은 아니다

본문의 나쁜 입력 [5, 3, 1, 2, 4]를 quick_sort로 정렬할 때, 각 단계의 피벗과 세 무리를 쓰고 재귀의 깊이를 구하세요.

3. 첫 값을 피벗으로 쓰면

pivot = values[len(values) // 2]를 pivot = values[0]으로 바꾼 퀵 정렬에 이미 정렬된 리스트 list(range(1000))를 넣으면 어떻게 될까요? 어떻게 고치면 될까요?

다음 장의 완전 이진 트리·힙·우선순위 큐에서는 가장 작은 값을 빠르게 꺼내는 자료구조인 힙을 만들고, 이를 이용해 최악의 경우에도 O(n log n)인 정렬로 이어 갑니다.