Algorithm 3 - Divide & Conquer

Master method(cookbook method)

T(n) = aT(n/b) + f(n) 형태의 recurrence를 해결하는 방법. (a는 number of subproblem, f(n)은 combining cost, b는 decreasing ratio)
위의 두 방법은 guessing으로 하기 때문에 완벽하게 올바르고 효율적인 방법을 찾아내기 어렵다. 따라서 이를 공식화한 것이다.

f(n)과 n^(logb(a)) 사이의 대소 비교를 통해 T(n)의 O(n)을 알아낼 수 있다. 만약 f(n)이 작다면 T(n) = O(n^(logb(a))), 같다면 T(n) = O(n^(logb(a)) * lgn), 더 크다면 T(n) = O(f(n))이 된다.

앞의 두 결과를 induction을 통해보면 분해와 결합 중 어느 것이 코스트가 크냐에 따라 전체 complexity가 정해지는 것을 알 수 있다. 따라서 master method는 결국 전체 점화식이 어느 항에 의해 최고차수가 되는지를 공식화 한 것이다.
 

Merge Sort
recursively 절반으로 나누고, 두 subarray를 합치면서 sorting을 진행.
이 때 Left half와 Right half를 합칠 때 각각의 첫 번째 index i, j 부터 하나씩 비교하여 작은 것을 찾아 합친 array의 왼쪽부터 (k) 놓으면 된다. 그리고 k는 계속 증가시키고, i와 j는 작은 것이 합쳐진 경우 +1씩 하면 된다.

Merge sort & Insertion sort combine
subarray의 size가 매우 작을 때는 insertion sort를 사용하는 것이 더 유리할 수 있다. 따라서 일정 크기 이하 (trashhold)를 잡고, 그 이하는 insertion sort를 사용하고, subarray의 크기가 커지면 merge sort를 사용할 수 있다.

이 경우 insertion sort가 시행되는 크기는 전체 array를 k개로 나눈 N/K가 되므로, best/worst case 모두 O(n)의 time complexity를 가진다.
Merge의 경우 전체 level의 개수는 lg(N/K)가 되고, N개의 element를 합쳐야 하므로 O(nlg(N/K))인 것을 알 수 있다.
best/worst case 모두에서 이 둘을 합한 time complexity는 O(n lg(N/K))가 된다. 이는 각각을 독립적으로 적용한 complexity인 O(nlgn)나 O(n^2)보다 좋다는 것을 알 수 있다.


Quick sort
일반적으로 많은 수의 데이터를 sorting 할 때 가장 효율적인 알고리즘으로 많이 사용된다.
pivot을 기준으로 대소를 비교하여 sub array로 분리하고, 다시 합치는 divide & conquer를 사용하는 방법. merge sort와 비슷하게 반복적으로 pivot을 정하고, sub array로 나누는 함수를 recursively call 한다.


배열의 pivot과 비교하여 element가 크거나 작거나 두 가지의 경우 밖에 없다. 만약 작다면 왼쪽 subarray와 swap하고, 만약 크다면 오른쪽 subarray에 그대로 두면 된다. 그리고 마지막으로 pivot을 올바른 위치에 넣으면 된다. (가장 오른쪽 원소를 pivot으로 잡는 경우)

*배열의 처음과 끝 : p, q, smaller subarray = p ~ i, larger subarray = i+1 ~ j, unsorted subarray = j+1 ~ q-1

이 때 중요한 것은 pivot을 기준으로 대소 비교를 하여 배열을 나누었기 때문에 pivot은 올바른 위치에 놓아지고,  따라서 그 다음 배열을 나눌 때는 pivot을 제외해도 된다. 이런 방식을 반복하여 단일 원소까지 나누다보면 모두 pivot이 되므로 합칠 때 비교할 필요가 없어 더 빠르다.
즉, partition 과정에 sorting이 포함되므로 나누고 합치기만 하면 분류된 결과를 얻을 수 있다.

단, pivot을 적절하게 설정하여 두 subarray가 비슷한 크기를 가지도록 해야 이진 트리가 생성되고 O(nlogn)의 time complexity를 가질 수 있다.
만약 한쪽으로 치우친 tree가 만들어지는 형태가 된다면 (Unbalanced partition) time complexity는 O(n^2)가 된다. (최악의 경우 pivot이 가장 작은 것, 혹은 가장 큰 것이 선택되어 하나씩 올바른 자리로 옮기는 insertion sort와 동일하게 되기 때문)

* already sorted array에 대한 quick sort 결과는 O(n^2)이 된다. 왜냐하면 위에서 말한 것 처럼 극단적으로 치우친 tree가 만들어지고, 각 단계마다 pivot만 제자리를 찾을 수 있기 때문이다.
배열의 원소 값이 모두 동일한 경우도 마찬가지이다.
- Randomized Quick sort
아이러니하게도, 일정 이상 sort된 배열에 quick sort를 사용하면 효율이 떨어진다. 따라서 pivot을 마지막/처음 원소로 선택하지 않고 임의의 위치에 있는 원소를 pivot으로 선택하는 것으로 이런 문제점을 막을 수 있다.

그러나 이런 랜덤성 역시 잘못된 원소를 선택할 가능성이 존재한다. 일반적으로 pivot의 최적값은 median을 사용하는 것인데, 전체 스캔을 한 번 해야 하므로 O(n)의 과정이 추가된다. 따라서 전체를 대상으로 하지 않고 몇 개를 선택하여 그 중에서 median을 선택하는 방법을 사용하여 이런 위험성을 줄일 수 있다. (Median of 3 method : 임의로 3개를 선택하여 그 중 median을 pivot으로 설정)

또한 앞서 merge & insertion sort를 합쳐서 작은 부분에서 insertion sort를 적용했던 것 처럼, quick sort에서도 작은 부분에 대해 insertion sort를 적용하여 조금 더 개선된 결과를 얻을 수 있다.