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)\) 알고리즘으로 부른다.
- 내부 정렬 (정렬 대상을 메모리에 다 올려두고 정렬해야 한다.)
- 가상 메모리 환경에서 잘 동작한다. 왜? =>Mergesort
- Divide and conquer 기반
- 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에 가깝게 동작한다.
즉 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
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
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
// 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
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