[Algo] 7.2 Performence of quicksort

worst-case partitioning
quicksort 的 worst-case 發生於 partitioning 完之後，產生一個 $n-1$ 跟 一個 0 的 subproblems，這代表切割點選的不是很好，這樣子我們可以把它的 running time 寫成如下的形式：
$T(n) = T(n - 1) + T(0) + \Theta(n) = T(n - 1) + \Theta(n)$
所以我們可以知道它的 running time 是 $\Theta(n^2)$，這代表 quicksort 並沒有比 insertion sort 好到哪裡去，而且更慘的是會發生在這種 worst-case 情況通常發生在 array 是已經呈現排序好的狀態，但是在這樣的情況下 insertion sort 只要 $O(n)$ 的 running time。


best-case partitioning
在 best-case 的情況下，代表 partitioning 完之後，產生一個 $\lfloor n/2 \rfloor$ 以及一個 $\lceil n/2 \rceil -1$ 的 subproblems，所以我們可以把它的 running time 寫成如下的形式：
$T(n) \leq 2T(n/2) + \Theta(n)$
根據 master theorem，我們可以知道 running time $T(n) = O(n \lg n)$


average-case partitioning
其實 average-case 跟 best-case 沒有差太多，我們來解釋一下為什麼。假設 PARTITION 演算法總是產生 9 比 1 的分割，我們可以得到如下的形式：
$T(n) \leq T(9n/10) + T(n/10) + cn$

看附圖可以知道整個 running time 還是 $O(n \lg n)$，即使是 99 比 1 的分割，整個 running time 還是 $O(n \lg n)$，因為產生任何常數比例的分割，都會讓整個 recursion tree 有 $\Theta(\lg n)$ 的高度，而每一層的 running time 都是 $O(n)$，所以 running time 都是 $O(n \lg n)$。