파티션의 목표#

파티션의 정확한 목표는 두 개의 서브 배열을 in-place 방식으로 적절하게 재배치해서
피벗 이하의 값은 왼쪽 영역에, 피벗 이상의 값은 오른쪽 영역에 오도록 재배치하는 것이다.

Lomuto 파티션#

대표적인 파티션 방법 2가지 중에 하나로 CLRS에서는 Lomuto 파티션을 기준으로 설명한다.

Lomuto 파티션의 수도 코드에서는 3가지를 보면 된다.

• 무엇을 피벗으로 잡았는지
• i와 j가 무엇을 나타내는 인덱스인지
• line 7-8에서 exchange하고 return하는게 무슨 의미인지

먼저 피벗 x를 마지막 원소값 $A[r]$ 로 잡는다.
Lomuto 방식에서 피벗을 꼭 마지막 값으로만 쓰는건 아닌데 CLRS에서는 그렇게 했다.

그리고 인덱스 i와 j를 포인터로 쓰는데
2개의 서브 배열의 포인터구나 <- 이렇게 넘겨짚으면 안된다.

i는 피벗보다 작거나 같은 값을 발견할 때마다 왼쪽부터 채워넣으려고 만든 인덱스이고
j는 피벗보다 작거나 같은 값을 탐색하기 위한 인덱스다.

반복문을 통해 피벗보다 작거나 같은 값의 탐색이 끝난 후 i가 위치한 곳은
피벗보다 작거나 같은 값으로 구성된 영역의 마지막 인덱스다.

그래서 그 다음 인덱스인 i+1의 값과 피벗값을 교환하면
i+1의 왼쪽은 모두 피벗 이하, 오른쪽은 피벗보다 큰 값으로 구성된다.

이 상태에서 피벗이 놓인 인덱스 i+1을 리턴하여 q라는 변수값에 넣고
그 값을 기준으로 왼쪽 영역 $A[p \ldots q-1]$과 오른쪽 영역 $A[q+1 \ldots r]$에 대해
다시 퀵 정렬을 재귀 호출한다. 피벗 $A[q]$는 이미 최종 위치에 있으므로 재귀 호출에서 제외함.

반복문의 각 회차가 시작될 때 배열의 각 구간은 다음 상태를 유지한다.

j가 한 칸 이동할 때마다 미분류 영역은 줄어들고,
$A[j] \le x$인 경우에만 i가 증가하면서 피벗 이하 영역이 넓어진다.

이렇게 반복문이 시작될 때마다 참이고, 반복이 한 번 끝난 뒤에도 계속 유지되는 조건을
루프 불변식(Loop invariant)이라고 한다.

파티션 방식마다 구체적인 불변식은 조금씩 다르니까 주의해야 한다.

Hoare 파티션#

CLRS에서는 연습 문제로 등장하는 Hoare 파티션이다.

보통 유튜브 쇼츠나 롱폼에 퀵 정렬 설명하는거 보면 양쪽에서 인덱스가 움직이는데
그게 바로 Hoare 파티션이다.

마찬가지로 피벗부터 먼저 선택하면 되는데, 수도 코드에서는 맨 처음 원소를 골랐다.

j는 오른쪽에서 시작해서 피벗 이하의 값을 찾을 때까지 왼쪽으로 이동하고
피벗 이하의 값을 찾으면 거기 잠시 주차한다

i는 반대로 왼쪽에서 시작해서 피벗 이상의 값을 찾을 때까지 오른쪽으로 이동하고
피벗 이상의 값을 찾으면 거기 잠시 주차한다.

그 후에 i가 j보다 작다면, 그러니까 둘이 교차되지 않았다면 둘의 값을 바꾼다.
i는 왼쪽에서 잘못 자리잡은 피벗 이상의 값을 가리키고, j는 오른쪽에서 잘못 자리잡은
피벗 이하의 값을 가리키고 있으므로 둘을 교환하면 각각 알맞은 영역으로 들어간다.

i는 피벗보다 작은 값들을 지나가다가 피벗 이상의 값을 만나면 멈추고,
j는 피벗보다 큰 값들을 지나가다가 피벗 이하의 값을 만나면 멈춘다.
이 과정을 반복하면 왼쪽의 피벗 이하 영역과 오른쪽의 피벗 이상 영역이 점점 넓어진다.

그러다가 i와 j가 만나거나 교차하면 j를 리턴한다.
이때 j는 피벗의 최종 위치가 아니라 왼쪽 영역의 마지막 인덱스이자 두 영역의 경계다.

따라서 왼쪽 영역은 $A[p \ldots j]$, 오른쪽 영역은 $A[j+1 \ldots r]$이 되고
각 영역에 대해 다시 퀵 정렬을 재귀 호출한다.
Lomuto와 달리 피벗이 반드시 j에 위치하는 것은 아니다.

피벗과 같은 값을 만나면 두 포인터가 모두 멈출 수 있는데
i < j라면 같은 값끼리라도 교환 과정을 거친다.

다음 반복에서 두 포인터가 다시 안쪽으로 이동해야 같은 위치에서 반복해서 멈추지 않기 때문이다.

파이썬 코드로 아래와 같이 구현할 수 있다.

1
def hoare_partition(arr, p, r):
2
    pivot = arr[p]
3
    i = p - 1
4
    j = r + 1
5

6
    while True:
7
        while True:
8
            j -= 1
9
            if arr[j] <= pivot:
10
                break
11

12
        while True:
13
            i += 1
14
            if arr[i] >= pivot:
15
                break
16

17
        if i < j:
18
            arr[i], arr[j] = arr[j], arr[i]
19
        else:
20
            return j
21

22

23
def quicksort(arr, p, r):
24
    if p < r:
25
        q = hoare_partition(arr, p, r)
26
        quicksort(arr, p, q)
27
        quicksort(arr, q + 1, r)

Hoare 파티션이 반환하는 q는 피벗의 최종 위치가 아니라 두 영역의 경계이므로
Lomuto 파티션과 다르게 왼쪽 재귀 범위에 q를 포함한다.

Lomuto와 Hoare 비교#

두 파티션은 피벗을 기준으로 배열을 두 영역으로 나눈다는 목적은 같다.
차이는 피벗을 처리하는 방법과 반환하는 인덱스의 의미에 있다.

Lomuto는 한 방향으로만 탐색해서 이해하기 쉽지만 교환 횟수가 많아질 수 있다.
Hoare는 양쪽에서 잘못 배치된 값을 한 번에 교환하기 때문에 일반적으로 교환 횟수가 더 적다.

중요한건 반환값의 의미와 재귀 범위를 한 세트로 기억하는 것이다.
두 방식의 파티션 코드와 재귀 범위를 섞어 쓰면 안된다.

균형 있게 나눈 경우#

피벗이 배열을 비슷한 크기의 두 영역으로 나눈다고 해보자.

각 재귀 깊이에서 파티션하는 원소 수를 모두 합하면 $n$이고,
배열의 크기를 절반씩 줄이면 재귀 깊이는 $\log n$이 된다.

따라서 시간복잡도는 다음과 같다.

한쪽으로 치우친 경우#

피벗이 매번 최솟값이나 최댓값으로 선택되면 한쪽에는 원소가 없고
다른 한쪽에는 나머지 원소가 전부 들어간다.

이 경우에는 재귀 깊이가 $n$이 되고, 전체 작업량은 다음과 같다.

첫 원소나 마지막 원소를 항상 피벗으로 고르면 이미 정렬된 배열에서 이런 상황이 발생할 수 있다.
무작위로 피벗을 선택하면 매번 균형 있게 나뉜다고 보장할 수는 없지만,
계속 최악의 피벗만 고를 가능성을 낮출 수 있다.

그래서 무작위 피벗을 사용하는 퀵 정렬의 기대 실행 시간은 $O(n \log n)$이다.