병합 정렬과 퀵 정렬: 분할 정복으로 정렬하기
값을 하나씩 끼워 넣는 정렬은 보통 n 이 두 배면 네 배쯤 느려집니다. 줄을 나눠서 작은 정렬 여러 개로 바꾸면 훨씬 빨라집니다. 막대 8개로 두 방법을 한 걸음씩 따라가 보세요.
한 줄 답. 둘 다 나눠서 풀고 합치는 분할 정복(divide and conquer) 정렬입니다. 병합 정렬은 줄을 반씩 자른 뒤, 정렬된 두 줄을 맨 앞끼리 비교하며 합칩니다(병합, merge). 퀵 정렬은 기준 값인 피벗(pivot) 하나를 골라 작은 것과 큰 것으로 먼저 나누고(분할, partition), 양쪽을 따로 정렬합니다. 반씩 나뉘면 층이 log₂n 개이고 층마다 n 번쯤 비교하므로 n·log n 번이 듭니다. 퀵 정렬은 피벗을 잘못 고르면 n² 이 되고, 피벗을 무작위로 고르면 그럴 일이 거의 없습니다.
「다음」을 누르면 한 걸음씩 나아가고, 아래에 무엇을 봤는지, 무엇을 했는지, 왜 그랬는지가 나옵니다. 옅은 바탕과 맨 아래 괄호가 지금 다루는 구간입니다. 화살표는 그 걸음에 한 일 하나만 그립니다. 병합 정렬: 초록(왼)과 파랑(오)이 왼쪽 반과 오른쪽 반, 주황 점선이 가운데 가르는 선입니다. 양쪽 화살표와 기호(5 > 2)가 두 맨 앞을 비교한 것이고, 아래로 가는 화살표가 「합친 줄」로 내려간 값, 흐린 테두리가 그 값이 떠난 자리입니다. 퀵 정렬: 주황과 「피벗」 화살표가 피벗입니다. 아래 괄호의 초록(< 3)은 피벗보다 작은 구역, 파랑(≥ 3)은 크거나 같은 구역, 회색(안 봄)은 아직 안 본 구역입니다. 서로 건너가는 화살표 둘이 교환이고, 옅은 주황과 ✓ 는 제자리에 놓여 끝난 값입니다.
1. 분할 정복: 나눠서 풀고 합친다
8개를 정렬하기는 어렵지만 1개를 정렬하기는 쉽습니다. 이미 정렬돼 있으니까요. 그래서 큰 문제를 같은 모양의 작은 문제로 나누고, 작은 답을 모아 큰 답을 만듭니다. 이 생각을 책에서는 분할 정복이라고 부릅니다. 함수가 자기 자신을 더 작은 입력으로 부르는(재귀, recursion) 코드가 됩니다.
| 분할 | 병합 | 일이 몰린 곳 | |
|---|---|---|---|
| 병합 정렬 | 가운데를 자른다. 생각할 것이 없다 | 정렬된 두 줄을 맨 앞끼리 비교하며 하나로 잇는다 | 병합 |
| 퀵 정렬 | 피벗을 골라 작은 쪽과 나머지로 가른다. 피벗은 제자리에 놓인다 | 할 일이 없다. 양쪽이 정렬되면 끝 | 분할 |
두 방법 모두 값을 서로 비교해서 정렬합니다. 그래서 일의 양을 「몇 번 비교했나」로 잽니다. 하나씩 끼워 넣는 정렬은 기초 정렬 쪽에, 「n 이 두 배면 몇 배」로 재는 법은 시간 복잡도 쪽에 있습니다.
2. 손으로 따라가기
실험과 같은 8개 5, 2, 7, 4, 8, 1, 6, 3 을 정렬합니다. 칸 번호는 왼쪽부터 1 ~ 8 입니다.
병합 정렬
반으로 자르기를 끝까지 하면 한 칸짜리 8개가 됩니다. 그다음 아래에서부터 합칩니다. 합치는 순서는 함수가 불리는 순서를 따라 왼쪽 절반을 먼저 끝냅니다.
| 합친 칸 | 왼쪽 | 오른쪽 | 결과 | 비교하지 않고 붙인 것(한쪽이 빈 뒤) | 비교 횟수 |
|---|---|---|---|---|---|
| 1–2 | [5] | [2] | [2, 5] | [5] | 1 |
| 3–4 | [7] | [4] | [4, 7] | [7] | 1 |
| 1–4 | [2, 5] | [4, 7] | [2, 4, 5, 7] | [7] | 3 |
| 5–6 | [8] | [1] | [1, 8] | [8] | 1 |
| 7–8 | [6] | [3] | [3, 6] | [6] | 1 |
| 5–8 | [1, 8] | [3, 6] | [1, 3, 6, 8] | [8] | 3 |
| 1–8 | [2, 4, 5, 7] | [1, 3, 6, 8] | [1, 2, 3, 4, 5, 6, 7, 8] | [8] | 7 |
| 합 | 17 | ||||
셋째 줄을 풀어 보면: 2 와 4 를 비교해 2 를 꺼냅니다. 5 와 4 를 비교해 4 를 꺼냅니다. 5 와 7 을 비교해 5 를 꺼냅니다. 왼쪽이 비었으니 남은 7 은 비교하지 않고 붙입니다. 3번입니다. 두 줄이 이미 정렬돼 있어서 맨 앞끼리만 보면 됩니다. 그래서 줄마다 비교 횟수는 「결과 개수 − 비교하지 않고 붙인 개수」입니다.
퀵 정렬(피벗 = 구간의 맨 끝 값)
구간의 맨 끝 값을 피벗으로 고르고, 앞에서부터 한 번 훑으며 피벗보다 작은 값을 앞으로 모읍니다. 끝에 피벗을 작은 쪽 바로 뒤로 옮기면 피벗은 제자리에 놓입니다. 구간에 값이 m 개면 피벗 말고 m − 1 개를 한 번씩 비교합니다.
| 구간(칸) | 피벗 | 작은 쪽 | 큰 쪽 | 나눈 뒤 줄 전체 | 비교 횟수 | 재귀 깊이 |
|---|---|---|---|---|---|---|
| 1–8 | 3 | [2, 1] | [4, 8, 5, 6, 7] | 2 1 3 4 8 5 6 7 | 7 | 1 |
| 1–2 | 1 | 없음 | [2] | 1 2 3 4 8 5 6 7 | 1 | 2 |
| 4–8 | 7 | [4, 5, 6] | [8] | 1 2 3 4 5 6 7 8 | 4 | 2 |
| 4–6 | 6 | [4, 5] | 없음 | 1 2 3 4 5 6 7 8 | 2 | 3 |
| 4–5 | 5 | [4] | 없음 | 1 2 3 4 5 6 7 8 | 1 | 4 |
| 합 | 15 | 4 | ||||
크기가 0 이나 1 인 구간은 나눌 것이 없어 건너뜁니다. 마지막 세 줄을 보세요. 4, 5, 6 은 이미 정렬돼 있어서 맨 끝 값이 늘 가장 크고, 큰 쪽이 비고, 구간이 한 칸씩만 줄어듭니다. 이것이 4절의 최악의 경우를 작게 본 모습입니다.
3. 왜 n·log n 인가
병합 정렬로 보면 쉽습니다. 8개를 반씩 자르면 8 → 4 → 2 → 1, 층이 3개입니다. 3 은 「2 를 몇 번 곱해야 8 이 되나」, 곧 log₂8 입니다. 그리고 한 층의 합치기를 모두 더하면 8개를 한 번씩 내려놓습니다. 크기 m 짜리를 합칠 때 많아야 m − 1 번 비교하니, 한 층에서 많아야 8번입니다.
| 층 | 조각 크기 | 병합 수 | 많아야(크기 − 1 씩) | 예제에서 |
|---|---|---|---|---|
| 1 | 1 → 2 | 4 | 4 | 4 |
| 2 | 2 → 4 | 2 | 6 | 6 |
| 3 | 4 → 8 | 1 | 7 | 7 |
| 합 | 7 | 17 (≤ 8 × 3 = 24) | 17 |
층이 log₂n 개, 층마다 n 번을 넘지 않으니 모두 n·log₂n 번을 넘지 않습니다. 이 예제는 마침 가장 많이 비교하는 경우(17번)입니다. 이미 정렬된 8개를 넣으면 합칠 때마다 한쪽이 먼저 비어서 12번입니다. algs4 는 위에서 아래로 가는 병합 정렬이 어떤 입력이든 ½·n·log₂n 번과 n·log₂n 번 사이로 비교한다고 적습니다(8개면 12 ~ 24).
n·log n 은 「n 이 두 배면 두 배보다 조금 더」입니다. n 이 두 배가 되면 층이 하나 늘 뿐이기 때문입니다. 1,024개면 층이 10개라 10,240번을 넘지 않습니다. 하나씩 끼워 넣는 정렬은 최악의 경우 n(n − 1) ÷ 2 = 523,776번이라 쉰 배쯤 차이가 납니다.
퀵 정렬도 피벗이 구간을 반씩 가르면 같은 계산이 됩니다. 층이 log₂n 개, 층마다 구간들을 한 번씩 훑어 n 번쯤입니다. 문제는 늘 반씩 갈린다는 보장이 없다는 것입니다.
4. 퀵 정렬이 n² 이 되는 때와 막는 법
피벗이 구간에서 가장 크거나 가장 작은 값이면 한쪽이 비고, 구간은 한 칸만 줄어듭니다. 이 일이 매번 일어나면 비교하는 횟수가 (n − 1) + (n − 2) + … + 1 = n(n − 1) ÷ 2, 곧 n² 에 비례합니다. n 이 두 배면 네 배입니다. 층도 log₂n 개가 아니라 n − 1 개로 깊어집니다. 이미 정렬된 입력에 「맨 끝 값」을 피벗으로 쓰면 정확히 이렇게 됩니다.
입력은 1 ~ n 이고, 「뒤섞임」과 「아무 값이나」는 고정 씨앗 난수기를 써서 같은 n 이면 늘 같은 결과가 나옵니다. 재귀 깊이(recursion depth)는 나누기가 일어난 가장 깊은 층입니다(맨 위가 1).
해 볼 것. ① 처음(뒤섞임, 맨 끝 값, n = 32)은 비교 횟수 175번, 깊이 10 입니다. n·log₂n = 160 과 비슷합니다. ② 「이미 정렬됨」을 누르면 496번, 깊이 31 이 됩니다. n(n − 1) ÷ 2 = 496 과 똑같고, 그림이 계단이 됩니다. 맨 끝 값이 늘 가장 큰 값이라 큰 쪽이 비기 때문입니다. ③ 그대로 「아무 값이나」를 누르면 138번, 깊이 8 로 돌아옵니다. ④ n 을 64 로 올리면 맨 끝 값은 2,016번(깊이 63), 아무 값이나는 354번(깊이 10)입니다. n 이 두 배가 될 때 앞의 것은 네 배쯤(496 → 2,016), 뒤의 것은 세 배가 안 됩니다(138 → 354).
막는 법.
- 피벗을 무작위로 고르거나, 정렬하기 전에 줄을 무작위로 섞습니다(셔플, shuffle). algs4 의 퀵 정렬은 먼저 섞습니다. 그러면 어떤 입력이 들어와도 최악의 경우가 나올 확률이 아주 작습니다. 나올 수는 있지만, 입력을 골라 일부러 일으키기는 어렵습니다.
- 몇 개를 뽑아 그 가운데 값을 피벗으로 씁니다. 예를 들어 세 값의 가운데 값(median-of-three)입니다. algs4 는 이것을 퀵 정렬을 빠르게 하는 방법으로 듭니다.
- 같은 값이 많으면 셋으로 나눕니다(3-way partitioning). 이 쪽의 단순한 나누기는 피벗과 같은 값을 모두 한쪽으로 보내서, 값이 모두 같으면 이것도 최악의 경우가 됩니다(같은 값 4개면 6번 = 4 × 3 ÷ 2). 작은 쪽, 같은 쪽, 큰 쪽으로 나누면 같은 쪽은 다시 정렬하지 않아도 됩니다.
5. 안정 정렬, 더 드는 메모리
| 병합 정렬 | 퀵 정렬 | |
|---|---|---|
| 같은 값의 순서(안정 정렬) | 지킨다. 합칠 때 두 맨 앞이 같으면 왼쪽 것을 먼저 꺼낸다(<=) | 지키지 않는다. 나눌 때 멀리 떨어진 두 칸을 교환한다 |
| 더 드는 메모리 | 합친 결과를 담을 옆 배열. n 에 비례 | 제자리에서 교환한다. 대신 나누어 들어간 깊이만큼 함수 호출이 쌓인다(실험의 깊이. 가장 나쁘면 n − 1) |
| 최악의 경우 | n·log n | n² |
| 일이 몰린 곳 | 병합 | 분할 |
안정 정렬은 값이 같은 것끼리 처음 순서를 지키는 정렬입니다. 숫자만 정렬할 때는 차이가 보이지 않지만, 주문을 날짜로 정렬하는 것처럼 값에 딸린 내용이 있으면 중요합니다. 예를 들어 주문을 고객 이름으로 정렬한 뒤 날짜로 다시 정렬하면, 안정 정렬에서는 같은 날짜 안에서 고객 이름 순서가 남습니다. 퀵 정렬로 2ᵃ, 2ᵇ, 1 을 나누면 피벗 1 보다 작은 것이 없어 1 이 맨 앞의 2ᵃ 와 자리를 교환하고 1, 2ᵇ, 2ᵃ 가 됩니다. 같은 2 끼리 순서가 뒤집혔습니다.
6. 언제 무엇을 쓰나
n·log n 은 「n 이 두 배면 두 배보다 조금 더」, n² 은 「n 이 두 배면 네 배」입니다.
| 선택지 | 최선의 경우 | 평균의 경우 | 최악의 경우 | 더 드는 메모리 | 안정 | 쓰는 경우 |
|---|---|---|---|---|---|---|
| 병합 정렬 | n·log n | n·log n | n·log n | n | 예 | 최악의 경우도 n·log n 이어야 할 때, 같은 값의 순서를 지켜야 할 때 |
| 퀵 정렬, 맨 끝 값을 피벗 | n·log n | n·log n | n²(정렬된 입력, 같은 값만) | 깊이만큼, 가장 나쁘면 n | 아니오 | 배우는 본보기. 실제로는 쓰지 않는다 |
| 퀵 정렬, 무작위 피벗 또는 먼저 셔플 | n·log n | n·log n | n², 나올 확률이 아주 작다 | 깊이만큼, 보통 log n 쯤 | 아니오 | 메모리를 더 쓰기 어렵고 순서를 지킬 필요가 없을 때 |
Python sorted(Timsort) | 이미 순서가 있으면 빨라진다 | n·log n | n·log n | n 에 비례 | 예 | Python 에서 정렬할 때는 거의 늘 이것 |
아주 작은 구간은 하나씩 끼워 넣는 기초 정렬로 바꿔 정렬하는 것이 algs4 가 드는 개선 방법입니다. 정렬 없이 가장 작은 것 몇 개만 필요하면 힙을, 정렬한 뒤 값을 찾을 때는 이진 탐색을 봅니다.
7. Python 으로
def merge_sort(xs):
if len(xs) <= 1:
return xs
mid = len(xs) // 2
left, right = merge_sort(xs[:mid]), merge_sort(xs[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= : 같은 값이면 왼쪽 것이 먼저(안정)
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]
print(merge_sort([5, 2, 7, 4, 8, 1, 6, 3])) # [1, 2, 3, 4, 5, 6, 7, 8]
def quick_sort(xs, lo=0, hi=None):
if hi is None:
hi = len(xs) - 1
if lo >= hi: # 값이 0~1개면 나눌 것이 없다
return xs
pivot, at = xs[hi], lo # 피벗 = 구간의 맨 끝 값
for i in range(lo, hi):
if xs[i] < pivot: # 피벗보다 작은 값만 앞으로
xs[i], xs[at] = xs[at], xs[i]
at += 1
xs[at], xs[hi] = xs[hi], xs[at] # 피벗을 제자리에
quick_sort(xs, lo, at - 1)
quick_sort(xs, at + 1, hi)
return xs
print(quick_sort([5, 2, 7, 4, 8, 1, 6, 3])) # [1, 2, 3, 4, 5, 6, 7, 8]
print(sorted([5, 2, 7, 4, 8, 1, 6, 3])) # 표준 라이브러리. 같은 결과, 안정 정렬
퀵 정렬은 실험과 같은 규칙(피벗 = 구간의 맨 끝 값, 로무토 분할)으로 적었습니다. 병합 정렬과 달리 새 리스트를 만들지 않고 받은 리스트 안에서 자리를 교환합니다.
Python 의 sorted 와 list.sort 는 Timsort 를 씁니다. Timsort 는 병합 정렬에 바탕을 두고, 자료에 이미 있는 정렬된 조각을 찾아 그대로 쓰기 때문에 거의 정렬된 자료에서 빠릅니다. Python 문서는 정렬이 안정 정렬임을 약속합니다. 그래서 「이름으로 정렬한 뒤 날짜로 다시 정렬」 같은 여러 번 정렬이 뜻대로 됩니다.
어디에 쓰나
- 언어의 정렬 함수 안. 직접 짤 일은 드물고, 그 함수가 어떤 성질(안정, 최악의 경우)을 약속하는지 알고 씁니다.
- 정렬된 두 목록 병합. 병합 정렬의 합치기만 떼어 쓰는 일이 많습니다. 정렬된 두 결과를 하나로 이을 때 처음부터 다시 정렬하지 않고 맨 앞끼리 비교하며 잇습니다. Python 에는
heapq.merge가 있습니다. - 메모리에 다 안 들어가는 큰 자료. 조각마다 정렬해 디스크에 쓰고, 정렬된 조각들을 병합 방식으로 합칩니다.
- 피벗으로 분할하기. 퀵 정렬의 나누기만 쓰면 「피벗보다 작은 것과 큰 것」을 한 번 훑어 가를 수 있습니다.
자주 묻는 것
일할 때 병합 정렬이나 퀵 정렬을 직접 짜야 하나요?
거의 없습니다. 언어가 주는 정렬 함수를 씁니다. Python 이면 sorted 나 list.sort 입니다. 직접 짜 보는 것은 속을 알기 위해서입니다. 속을 알면 왜 정렬이 n·log n 인지, 같은 값의 순서가 왜 지켜지는지, 어떤 입력에서 느려질 수 있는지를 판단할 수 있습니다.
퀵 정렬은 왜 안정 정렬이 아닌가요?
나눌 때 멀리 떨어진 두 칸을 교환하기 때문입니다. 2ᵃ, 2ᵇ, 1 을 이 쪽의 퀵 정렬로 나누면 피벗 1 보다 작은 것이 없어 1 이 맨 앞의 2ᵃ 와 자리를 교환하고, 1, 2ᵇ, 2ᵃ 가 됩니다. 같은 값 2 끼리의 순서가 뒤집혔습니다.
피벗을 무작위로 고르면 결과가 매번 달라지나요?
정렬된 결과는 같습니다. 달라지는 것은 비교 횟수와 깊이입니다. 다만 퀵 정렬은 안정 정렬이 아니라서, 값은 같고 딸린 내용이 다른 자료(같은 날짜의 주문 여럿)라면 같은 값끼리의 순서는 달라질 수 있습니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 나눠서 풀고 합치기 | 분할 정복(divide and conquer) |
| 정렬된 두 줄 합치기 | 병합(merge), 병합 정렬(mergesort) |
| 기준 값 | 피벗(pivot) |
| 작은 쪽과 큰 쪽으로 가르기 | 분할(partition) |
| 함수가 자기를 다시 부르기 | 재귀(recursion). 깊이는 재귀 깊이(recursion depth) |
| 값끼리 비교한 횟수 | 비교 횟수(compares) |
| 같은 값의 순서를 지키는 정렬 | 안정 정렬(stable sort) |
| 옆 배열 없이 제자리에서 | 제자리 정렬(in-place sort) |
| 무작위로 섞기 | 셔플(shuffle) |
| 세 값의 가운데 값 | median-of-three |
| 작은 쪽, 같은 쪽, 큰 쪽으로 가르기 | 3-way partitioning |
| n·log n, n² | O(n log n), O(n²). 선형 로그 시간(linearithmic), 이차 시간(quadratic) |
출처
- Robert Sedgewick, Kevin Wayne, Algorithms 4th ed., 2.2 Mergesort. 위에서 아래로 가는 병합 정렬, ½·n·log₂n ~ n·log₂n 번의 비교, n 에 비례하는 옆 공간.
- Robert Sedgewick, Kevin Wayne, Algorithms 4th ed., 2.3 Quicksort. 먼저 섞기, 가장 나쁠 때 n²/2 번의 비교, 가운데 값으로 기준 고르기, 셋으로 나누기.
- Python 문서, Sorting Techniques. 정렬이 안정 정렬임을 약속한다는 것, Timsort, 여러 번 정렬하기.
- CPython 소스, listsort.txt. Timsort 가 병합 정렬에 바탕을 둔 안정 정렬이라는 것, 이미 순서가 있는 입력에서 견주는 횟수가 줄어든다는 것, 더 드는 메모리.