[Algo] 7.1 Description of quicksort

quicksort 的原理
一樣是 divide and conquer 的方法，假設 $A[p \ldots r]$ 是我們想要做排序的 array，那我們先找一個 element 來當作基準值(pivot)，把 $A[p \ldots r]$ 分成 $A[p \ldots q-1]$，$A[q]$，$A[q+1, \ldots r]$ 三部份，其中 $A[p \ldots q-1]$ 為所有比 $A[q]$ 小的 elements，$A[q+1, \ldots r]$ 為比 $A[q]$ 大的 elements。接著 $A[p \ldots q-1]$ 跟 $A[q+1 \ldots r]$ 這兩個 subarrays 再繼續用這個方法分下去，(找出一個 pivot，然後把 array 分成比 pivot 小的放一邊，比 pivot 大的放另外一邊)分到最後當 arrary 的 size 只剩3個 elements 的時候，其實我們這時候就可以說是到了 recursion 的終點了，整個排序也就完成了。


quicksort 的 pseudocode
@{
\proc{Quicksort}(A, p, r)
\li \If p < r
\li \;\;\;\;q = \proc{Partition}(A, p, r)
\li \;\;\;\;\proc{Quicksort}(A, p, q - 1)
\li \;\;\;\;\proc{Quicksort}(A, q + 1, r)
}@

@{
\proc{Partition}(A, p, r)
\li x = A[r]
\li i = p - 1
\li \For j = p \;\textbf{to}\;r - 1
\li \;\;\;\;\If A[j] \leq x
\li \;\;\;\;\;\;\;\;i = i + 1
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[j]
\li \textup{exchange}\;A[i+1]\;\textup{and}\;A[r]
\li \Return i + 1
}@

PARTITION 解說
(1) 直接律定 array 的最後一個 element $A[r]$ 為 pivot
(2) 從 $A[p]$ 開始 scan 到 $A[r-1]$，在每個 loop 都保持這樣的 property：
    (a) $A[p \ldots i]$ 都是比 pivot 小的 elements
    (b) $A[i+1 \ldots j-1]$ 都是比 pivot 大的 elements
(3) 最後把 pivot 放到分界點 $A[i+1]$

對 $A[p \ldots r]$ 執行 PARTITION 的 running time 是 $\Theta(n)$，其中 $n = r - p + 1$。