Quicksort

Quicksort 기본 동작 방식

• ko.wikipedia.org/wiki/퀵 정렬 일단 기본적인 동작 방식은 이걸 참고.
• en.wikipedia.org/wiki/Quicksort 목차를 보면 영문 위키가 더 상세하다. pivot 고르는 법, 다양한 퀵소트
• wiki/Sorting_algorithm#Comparison_of_algorithms

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

• https://www.geeksforgeeks.org/dual-pivot-quicksort/
• https://github.com/umbum/Algorithm/blob/master/DualPivotQuick/DualPivotQuick/dual_pivot.c

여러가지 방식의 QuickSort

wiki/Quicksort sudo code

Introduction To Algorithm에 나온 방법.

• 맨 우측 pivot
• 왼쪽에서 i, j가 함께 출발
• j가 pivot 위치까지 진행
• j는 항상 증가, i는 스왑 할 때만 증가. (j가 p보다 작으면 ij 스왑.)
• i의 왼쪽에는 항상 pivot 보다 작은 항목만 존재하도록 하는 것이 핵심.

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 돌려보면 이렇게.

// 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을 포함하지 않도록 짤 때

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이 다음 재귀 한 쪽에 포함된다. 그래서 자명하지 않다.