[Algo] 7.4 Analysis of quicksort

7.4.1 Worst-case analysis
我們現在將要來證明一下，在 worst-case 的 split 下，整個 quicksort 的 running time 是 $\Theta(n^2)$。我們要使用的方法是 substitution method，我們先證明整個 running time 是 $O(n^2)$。
令 $T(n)$ 是對一個長度為 n 的 sequence 執行 quicksort 的 worst-case running time。我們可以得到如下的表示：
$$T(n) = \max_{0 \leq q \leq n-1} (T(q) + T(n - 1 - q)) + \Theta(n)$$其中 q 的範圍是從 0 到 n-1，因為 quicksort 會 split 成兩個 subproblem。

使用 substitution method，我們猜想 $T(n) \leq cn^2$，其中 c 是個常數。把這個猜想代入上一個式子我們會得到：


其中 $q^2 + (n - 1 - q)^2$ 在 $q = 0$ 或 $q = n-1$ 時才會有極大值，所以我們可以知道$$q^2 + (n - 1 - q)^2 \leq (n - 1)^2 \leq n^2 - 2n + 1$$
由此可知，
$$T(n) \leq c(n^2 - 2n + 1) + \Theta(n) = cn^2 -c(2n - 1) + \Theta(n) \leq cn^2$$
因為我們總是可以選一個適當的常數 c 來讓 $c(2n - 1)$ 這一項比 $\Theta(n)$ 這一項還來的大。所以我們就可以證明出 $T(n) = O(n^2)$

7.4.2 Expected running time
quicksort 的 running time 主要是花在 PARTITION 這個 procedure 上面。所以要分析 quicksort 最好就是從 PARTITION 這個 procedure 上面下手。值得注意的事情是，每一次 call PARTITION 這個 procedure 的時候，總是會有一個 pivot 被選上，而且這個 pivot 在往後的 recursion call 是不會繼續參與到的，換句話說，在整個 quicksort 的演算法，PARTITION 這個 procedure 最多只會被 call 到 n 次而已。
而 PARTITION 這個 procedure 的 running time 跟第 3～6 行的 for loop 迴圈次數有關，也就是說如果我們可以算出第 4 行總共被執行到幾次 的話，我們就可以得到 quicksort 的 running time。

Lemma 7.1
Let X be the number of comparisons performed in line 4 of PARTITION over the entire execution of QUICKSORT on an n-element array. Then the running time of QUICKSORT is $O(n + X)$.

所以我們現在著眼於算出 X，令 array A 裡的 elements 為 $z_1, z_2, \ldots, z_n$，其中 $z_i$ 為第 i 小的 element。另外，我們也定義集合 $Z_{ij} = \{z_i, z_{i+1}, \ldots, z_j\}$ 為從 $z_i$ 到 $z_j$ 之間的所有 elements。此外，我們也定義一個 indicator random variable $X_{ij} = I\{z_i \mbox{ is compared to } z_j\}$，由此我們可以知道
$$X = \sum_{i = 1}^{n-1}\sum_{j = i+1}^n X_{ij}$$
於是我們可以得到
$$E[X] = E[\sum_{i = 1}^{n-1}\sum_{j = i+1}^n X_{ij}] = \sum_{i = 1}^{n-1}\sum_{j = i+1}^n E[X_{ij}] = \sum_{i = 1}^{n-1}\sum_{j = i+1}^n  \mbox{Pr} \{z_i \mbox{ is compared to } z_j\} $$
接下來我們就剩下看看如何算這個機率了，假設現在有一個 input 是 $A = \{1, 2, \ldots, 10\}$， 當我們 call quicksort 的時候，假設第一次選到的 pivot 是 7，那麼 PARTITION 會把 array A 分成兩個 subproblems：$\{1, 2, 3, 4, 5, 6\}$ 和 $\{8, 9, 10\}$，在這樣的情況下 pivot 7 會和這兩個 sets 的所有 number 做 comparison，但是第一個 set 裡面的 number 絕對不會和第二個 set 裡面的任何一個數字 compare 到。
一般來說，一旦 x 被選到成為 pivot，那麼對任何兩個 $z_i$ 和 $z_j$，如果 $z_i < x < z_j$ 的話，$z_i$ 和 $z_j$ 是不會比到大小的。所以對一個 set $Z_{ij}$ 來說，除非 $z_i$ 或 $z_j$ 被選為 pivot，否則 $z_i$ 和 $z_j$ 是不會作到 comparison 的。舉例：7 被選為 pivot 的時候，$Z_{2,9}$ 的 2 和 9 是不會比到大小的。
假設 $Z_{ij}$ 裡的所有 numbers 被選為 pivot 的機率都一樣，那每一個 number 被選為 pivot 的機率就是：$1/(j - i +1)$。所以 Pr{$z_i$ is compared to $z_j$} = Pr{$z_i$ or $z_j$ is the first pivot chosen from $Z_{ij}$} = Pr{$z_i$ is the first pivot chosen from $Z_{ij}$} + Pr{$z_j$ is the first pivot chosen from $Z_{ij}$} = $2/(j - i + 1)$，所以我們可以得到：
$$E[X] = \sum_{i = 1}^{n-1}\sum_{j = i + 1}^n \frac{2}{j-i+1} < \sum_{i = 1}^{n-1}\sum_{j = i + 1}^n \frac{2}{j-i} = \sum_{i = 1}^{n-1}O(\lg n) = O(n \lg n)$$
於是我們可以得證 RANDOMIZED-PARTITION 的 expected running time 是 $O(n \lg n)$