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 java.util.Arrays.sort()``의 경우 데이터 타입에 대해서는 Dual pivot Quicksort를, ``java 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 보다 작은 항목만 존재하도록 하는 것이 핵심.

```py

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

```py

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