병합 정렬과 퀵 정렬: 분할 정복으로 정렬하기

값을 하나씩 끼워 넣는 정렬은 보통 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번입니다. 두 줄이 이미 정렬돼 있어서 맨 앞끼리만 보면 됩니다. 그래서 줄마다 비교 횟수는 「결과 개수 − 비교하지 않고 붙인 개수」입니다.

왼쪽 오른쪽 2547 ① 2 < 4 → 2 ② 5 > 4 → 4 ③ 5 < 7 → 5 ④ 왼쪽이 빔: 7 그대로 합친 줄 2457 ①②③④
셋째 줄(칸 1–4) 합치기. 번호가 내려가는 순서입니다. 맨 앞끼리 세 번 비교하고(①②③), 왼쪽이 빈 뒤 남은 7 은 비교하지 않고 붙습니다(④, 점선).

퀵 정렬(피벗 = 구간의 맨 끝 값)

구간의 맨 끝 값을 피벗으로 고르고, 앞에서부터 한 번 훑으며 피벗보다 작은 값을 앞으로 모읍니다. 끝에 피벗을 작은 쪽 바로 뒤로 옮기면 피벗은 제자리에 놓입니다. 구간에 값이 m 개면 피벗 말고 m − 1 개를 한 번씩 비교합니다.

구간(칸)피벗작은 쪽큰 쪽나눈 뒤 줄 전체비교 횟수재귀 깊이
1–83[2, 1][4, 8, 5, 6, 7]2 1 3 4 8 5 6 771
1–21없음[2]1 2 3 4 8 5 6 712
4–87[4, 5, 6][8]1 2 3 4 5 6 7 842
4–66[4, 5]없음1 2 3 4 5 6 7 823
4–55[4]없음1 2 3 4 5 6 7 814
합154

크기가 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 씩)예제에서
11 → 2444
22 → 4266
34 → 8177
합717 (≤ 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).

막는 법.

5. 안정 정렬, 더 드는 메모리

병합 정렬퀵 정렬
같은 값의 순서(안정 정렬)지킨다. 합칠 때 두 맨 앞이 같으면 왼쪽 것을 먼저 꺼낸다(<=)지키지 않는다. 나눌 때 멀리 떨어진 두 칸을 교환한다
더 드는 메모리합친 결과를 담을 옆 배열. n 에 비례제자리에서 교환한다. 대신 나누어 들어간 깊이만큼 함수 호출이 쌓인다(실험의 깊이. 가장 나쁘면 n − 1)
최악의 경우n·log nn²
일이 몰린 곳병합분할

안정 정렬은 값이 같은 것끼리 처음 순서를 지키는 정렬입니다. 숫자만 정렬할 때는 차이가 보이지 않지만, 주문을 날짜로 정렬하는 것처럼 값에 딸린 내용이 있으면 중요합니다. 예를 들어 주문을 고객 이름으로 정렬한 뒤 날짜로 다시 정렬하면, 안정 정렬에서는 같은 날짜 안에서 고객 이름 순서가 남습니다. 퀵 정렬로 2ᵃ, 2ᵇ, 1 을 나누면 피벗 1 보다 작은 것이 없어 1 이 맨 앞의 2ᵃ 와 자리를 교환하고 1, 2ᵇ, 2ᵃ 가 됩니다. 같은 2 끼리 순서가 뒤집혔습니다.

나누기 전나눈 뒤 피벗 2ᵃ2ᵇ1 12ᵇ2ᵃ 서로 교환
피벗 1 보다 작은 값이 없어 1 이 맨 앞 2ᵃ 와 서로 건너가 자리를 교환합니다. 가운데 2ᵇ 는 그대로라 같은 2 끼리 순서가 2ᵃ, 2ᵇ 에서 2ᵇ, 2ᵃ 로 뒤집힙니다.

6. 언제 무엇을 쓰나

n·log n 은 「n 이 두 배면 두 배보다 조금 더」, n² 은 「n 이 두 배면 네 배」입니다.

선택지최선의 경우평균의 경우최악의 경우더 드는 메모리안정쓰는 경우
병합 정렬n·log nn·log nn·log nn예최악의 경우도 n·log n 이어야 할 때, 같은 값의 순서를 지켜야 할 때
퀵 정렬, 맨 끝 값을 피벗n·log nn·log nn²(정렬된 입력, 같은 값만)깊이만큼, 가장 나쁘면 n아니오배우는 본보기. 실제로는 쓰지 않는다
퀵 정렬, 무작위 피벗 또는 먼저 셔플n·log nn·log nn², 나올 확률이 아주 작다깊이만큼, 보통 log n 쯤아니오메모리를 더 쓰기 어렵고 순서를 지킬 필요가 없을 때
Python sorted(Timsort)이미 순서가 있으면 빨라진다n·log nn·log nn 에 비례예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 이면 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)

출처

← 기초 정렬: 버블·선택·삽입힙과 우선순위 큐 →