Post

Quicksort

Quicksort 기본 동작 방식

Worst case : \(\Theta(n^2)\) Best case : \(\Theta(n\lg n)\) Average case : \(\Theta(n\lg n)\)에 근사

대부분의 케이스에 \(\Theta(n\lg n)\)로 동작하며 여기에 숨겨진 상수 인자도 매우 작기 때문에 Worst는 \(\Theta(n^2)\)이지만 \(\Theta(n\lg n)\) 알고리즘으로 부른다.

  1. 내부 정렬 (정렬 대상을 메모리에 다 올려두고 정렬해야 한다.)
  2. 가상 메모리 환경에서 잘 동작한다. 왜? =>Mergesort
  3. Divide and conquer 기반
  4. in-place 정렬

실제로 java.util.Arrays.sort()의 경우 데이터 타입에 대해서는 Dual pivot Quicksort 를, Object 타입에 대해서는 Mergesort 를 사용한다. 코틀린은 이를 가져와 사용하므로 코틀린도 마찬가지.

Worst case / Best case 비교

Quicksort의 Best case와 Worst case는 직접 진행해보면 직관적으로 이해 가능하다.

Worst case : 부분 배열이 한 쪽으로 편중되어 나뉘는 경우 pivot으로 선택되어 위치가 고정되는 원소의 개수가 줄어들기 때문에 비교 횟수가 각 라운드마다 1씩만 감소한다.

Base case : 수행 시간을 줄이기 위해서는 한 번 비교 시 두 개의 역을 제거해야 한다(위치가 고정되는 원소의 개수가 두 개여야 한다) 따라서 pivot이 위치하게 되는 split point가 배열의 중앙에 가까울 수록 Best case에 가깝게 동작한다.

Worst case(왼쪽) / Best case(오른쪽)

즉 pivot을 어디서 뽑든 간에, 중앙을 잘 나누는 값이 선택되었느냐가 중요하다.

  • 배열이 이미 오름차순으로 정렬되어 있을 때 단순히 맨 좌측 값을 pivot으로 선택한다면 맨 좌측/나머지로 분할되기 때문에 Worst case가 된다.
  • 이렇게 이미 sorting된 배열이 들어왔을 때의 성능 문제는 정 중앙에 위치한 element (middle index)를 pivot으로 뽑으면 해결되긴 한다.
  • 이를 좀 더 개선한, 세 값(좌측 끝, 중앙, 우측 끝)의 중위값(median)을 계산하여 그를 pivot으로 뽑는 방법이 있고 실제 많은 라이브러리에서 사용 중이다. 이를median-of-three rule 이라 부른다. Pivot을 뽑은 다음 맨 우측과 자리 바꾸고 알고리즘 돌리면 된다. (어차피 1cycle 돌리면 pivot이 다시 중앙으로 이동하며 고정된다.)

Dual pivot Quicksort

여러가지 방식의 QuickSort

wiki/Quicksort sudo code

Introduction To Algorithm에 나온 방법.
  • 맨 우측 pivot
  • 왼쪽에서 i, j가 함께 출발
  • j가 pivot 위치까지 진행
  • j는 항상 증가, i는 스왑 할 때만 증가. (j가 p보다 작으면 ij 스왑.)
  • i의 왼쪽에는 항상 pivot 보다 작은 항목만 존재하도록 하는 것이 핵심.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quickSort(A, left, right):
if (left < right):
split = partition(A, left, right)
quickSort(A, left, split - 1)
quickSort(A, split + 1, right)


def partition(A, left, right):
p = right
i = left
j = left
while (j < right):
if (A[j] < A[p]):
swap(A, i, j)
i += 1
j += 1
swap(A, i, p)
return i

1cycle 돌려보면 이렇게.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// index는 loop 진입 시점의 상태를 나타냄
   5 - 3 - 7 - 6 - 2 - 1 - 4
   j=0    ij                      p
   j=1    i   j                   p  // swap
   3 - 5 - 7 - 6 - 2 - 1 - 4
   j=2        i   j               p
   j=3        i       j           p
   j=4        i           j       p  // swap
   3 - 2 - 7 - 6 - 5 - 1 - 4
   j=5            i           j   p  // swap
   3 - 2 - 1 - 6 - 5 - 7 - 4
   j=6                i           jp  // 종료 swap
   
  3 - 2 - 1 | 4 | 5 - 7 - 6
   fix

양끝에서 i,j가 출발하도록 짜면 지저분해진다.
  • 맨 좌측 pivot
  • 양끝에서 i, j가 출발하고
  • do while을 안쓰면서
  • i, j의 움직임에 pivot을 포함하지 않도록 짤 때
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def partition2(A, left, right):
## [2, 1] 들어오는 케이스, [1, 2] 들어오는 케이스도 생각 해봐야 함.
p = left
i = left + 1
j = right
while (True):
while (i < right and A[i] < A[p]):
i += 1
while (j > left + 1 and A[j] > A[p]):
j -= 1


if (i < j):
swap(A, i ,j)
else:
if (A[p] > A[j]):
swap(A, p, j)


return j

Hoare의 분할은 quickSort 함수 부터가 좀 다르다. pivot이 다음 재귀 한 쪽에 포함된다. 그래서 자명하지 않다.
This post is licensed under CC BY 4.0 by the author.