엄범


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. 가상 메모리 환경에서 잘 동작한다. 이는 히트율이 높다는 의미인 듯.
  3. Divide and conquer 기반
  4. in-place이나 약간 주의해야 하는 점이 있다.

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


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

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

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

즉 `` pivot``이 중앙을 잘 나누도록 선택하는 것이 중요한데, 배열이 이미 오름차순으로 정렬되어 있을 때 단순히 맨 좌측 값을 `` pivot``으로 선택한다면 맨 좌측/나머지로 분할되기 때문에 Worst case가 된다.


Dual pivot Quicksort

https://github.com/umbum/Algorithm/blob/master/DualPivotQuick/DualPivotQuick/dual_pivot.c


여러가지 방식의 QuickSort 

wiki/Quicksort sudo code


(맨 좌측 pivot) (양끝에서 i, j가 출발하고) (do while을 안쓰면서) (i, j의 움직임에 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):

    # [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

```


(맨 우측 pivot) (왼쪽에서 i, j가 함께 출발) (j가 pivot 위치까지 갈 수 있음) Introduction To Algorithm에 나온 방법.

```py

def partition2(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

```


Hoare의 분할은 quickSort 함수 부터가 좀 다르다. pivot이 다음 재귀 한 쪽에 포함된다. 그래서 자명하지 않다.


'Algorithm > Theory' 카테고리의 다른 글

점근적 표기 / 평균 수행 시간 분석  (0) 2018.04.20
피보나치 수  (0) 2018.04.20
Quicksort  (0) 2018.04.08
Primality test  (0) 2017.11.19
재귀, recursion  (0) 2017.05.31
P, NP, NP-hard, NP-complete  (0) 2016.08.15