# Lecture 06 - Quick sort
> 課程內容 : 中興大學資工系 范耀中教授 (112 學年度第 2 學期)
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

快速排序法(Quick sort)與 Merge sort 類似，都是使用 divide and conquer 的概念，將大的陣列分成小問題後逐一解決。但 Quick sort 引入了分割(partition)的概念來分割小問題

## 1. Quick sort 演進
### 1.1 Idea (1): Partition items 分割
> Procedure
> 1. 選擇一個基準(pivot)
> 2. 從左開始掃描，比基準小的放左側，比基準大的放右側
> 3. 結束後該基準就會是在正確的位置，且左右分別有比基準小/大的子陣列
> 4. 對左右的子陣列繼續做上述動作

假設陣列 `[4, 2, 6, 1, 5, 7, 3]` 並以 `4` 作為基準

| Scan | Comparison | Left array | Right array |
| :-: | :- | :- | :- |
| 4 | Nothing | `[ ]` | `[ ]` |
| 2 | Less than | `[2]` | `[ ]` |
| 6 | Greater than | `[2]` | `[6]` |
| 1 | Less than | `[2, 1]` | `[6]` |
| 5 | Greater than | `[2, 1]` | `[6, 5]` |
| 7 | Greater than | `[2, 1]` | `[6, 5, 7]` |
| 3 | Less than | `[2, 1, 3]` | `[6, 5, 7]` |

最後結果為 `[2, 1, 3, 4, 6, 5, 7]`，可以發現基準元素 `4` 已經排好，且左邊是比 `4` 小的陣列，右邊是比 `4` 大的陣列。再繼續對左邊及右邊做排序


:::info
複雜度 : $N \cdot \log N$
缺點 : 浪費兩倍的記憶體空間
:::


### 1.2 Solution : In-place
> Procedure
> 1. 同樣選擇一個基準(pivot)元素
> 2. 由左至右開始掃描整個陣列
> 3. 若遇到比基準值大的元素，就從陣列尾端**依序**拿一個元素做交換
> 4. 若遇到比基準值小的元素，就直接與基準值交換
> 5. 直到所有元素都被交換過，則該基準值已被排好
> 6. 同樣可以得到兩個子陣列，依序做上述操作

假設陣列 $[4,\ 5,\ 3,\ 1,\ 6,\ 7,\ 8]$ 並以 $4$ 作為基準

| Scan | Comparison | Result |
| :-: | :-: | :-: |
| 4 | Nothing | $[4,\ 5,\ 3,\ 1,\ 6,\ 7,\ 8]$ |
| 5 | $>$ | $[4,\ 8,\ 3,\ 1,\ 6,\ 7,\ \bf{5}]$ |
| 8 | $>$ | $[4,\ 7,\ 3,\ 1,\ 6,\ \bf{8},\ \bf{5}]$ |
| 7 | $>$ | $[4,\ 6,\ 3,\ 1,\ \bf{7},\ \bf{8},\ \bf{5}]$ |
| 6 | $>$ | $[4,\ 1,\ 3,\ \bf{6},\ \bf{7},\ \bf{8},\ \bf{5}]$ |
| 1 | $<$ | $[1,\ 4,\ 3,\ \bf{6},\ \bf{7},\ \bf{8},\ \bf{5}]$ |
| 3 | $<$ | $[1,\ 3,\ 4,\ \bf{6},\ \bf{7},\ \bf{8},\ \bf{5}]$ |

**註 : 粗體字表示已經換過位置**

到最後因為 $6$ 已經交換過位置，因此排序結束且基準元素 $4$ 已經排好位置，左右兩側分別是比 $4$ 小/大的子陣列，將左右子陣列依序做上述操作


:::info
優點 : 只需要一個 Array 的空間
缺點 : 會產生不必要的搬移，例如一開始明明 $5>4$ 但卻換了一個更大的 $8$ 來到前面
:::

### 1.3 Solution : 避免不必要的搬移
> Procedure
> 1. 同樣選定一個基準值(pivot)
> 2. 從陣列左右兩側同時做掃瞄
> 3. 左側(Left scan pointer)尋找比基準值大的元素
> 4. 右側(Right scan pointer)尋找比基準值小的元素
> 5. 找到以後做交換
> 6. 當左右交錯後，掃描停止，並取當前基準值與 Right scan pointer 交換

假設陣列 $[4,\ 5,\ 3,\ 1,\ 6,\ 7,\ 2,]$ 並以 $4$ 作為基準值

| Left pointer | Array | Right pointer |
| :-: | :-: | :-: |
| 5 | $[4,\ \overline 5,\ 3,\ 1,\ 6,\ 7,\ \mathbf{2},]$ | 2 |
| 3 | $[4,\ 2,\ \overline 3,\ 1,\ 6,\ \mathbf{7},\ 5,]$ | 7 |
| 1 | $[4,\ 2,\ 3,\ \overline 1,\ \mathbf{6},\ 7,\ 5,]$ | 6 |
| 6 | $[4,\ 2,\ 3,\ \mathbf{1},\ \overline 6,\ 7,\ 5,]$ | 1 |
| | $[\mathbf{1},\ 2,\ 3,\ 4,\ \overline 6,\ 7,\ 5,]$ | |

基準值 $4$ 已經排好，左右兩側分別為比 $4$ 小與大的子陣列，兩側繼續做上述操作


以上改進後的版本就是 Quick sort 的核心內容

#### 缺點
考慮遞減排序的陣列 $[7,\ 6,\ 5,\ 4,\ 3,\ 2,\ 1]$ 並以 $7$ 作為基準值

| Left pointer | Array | Right pointer |
| :-: | :-: | :-: |
| 6 | $[7,\ \overline 6,\ 5,\ 4,\ 3,\ 2,\ \mathbf{1}]$ | 1 |
| 5 | $[7,\ 6,\ \overline 5,\ 4,\ 3,\ 2,\ \mathbf{1}]$ | 1 |
| 4 | $[7,\ 6,\ 5,\ \overline 4,\ 3,\ 2,\ \mathbf{1}]$ | 1 |
| 3 | $[7,\ 6,\ 5,\ 4,\ \overline 3,\ 2,\ \mathbf{1}]$ | 1 |
| 2 | $[7,\ 6,\ 5,\ 4,\ 3,\ \overline 2,\ \mathbf{1}]$ | 1 |
| 1 | $[7,\ 6,\ 5,\ 4,\ 3,\ 2,\ \overline{\mathbf{1}}]$ | 1 |
| | $[\overline{\mathbf{1}},\ 6,\ 5,\ 4,\ 3,\ 2,\ 7]$ | |

從上述會發現排完後的陣列是 $[1,\ 6,\ 5,\ 4,\ 3,\ 2,\ 7]$，但尚未排序完成

## 2. Quick sort analysis
### 2.1 Best and worse case
由上述最後的例子可以發現 quick sort 的 worse case 以及 best case 所對應的情況。當挑選到最大或最小值作為基準值時，就是 quick sort 的 worse case，因為第一次 scan 後的結果這個基準值會在最左側或是最右側，此時的樹狀圖會是斜的 (如下圖)，複雜度為 $(N-1)+(N-2)+...=\cfrac{N^2}{2}$


而 quick sort 的 best case ，是當選到的基準值是中位數，此時做完第一次 scan 後基準值會在中間，兩側的 sub-tree 會是平均分配的，複雜度是 $N \times \log N$。

### 2.2 Average case
假設 N 個元素的 array 做 quick sort 的複雜度是 $C_N$

$$
C_N = (N+1) + \frac{C_0+C_{N-1}}{N} + \frac{C_1+C_{N-2}}{N} + ... + \frac{C_{N-1}+C_{0}}{N}
$$

其中，

* $N+1$ 表示 left scan 與 right scan 掃過整個 array 並交錯的次數
* $\cfrac{C_0+C_{N-1}}{N}$ 中，$C_0+C_{N-1}$ 表示選到最小值 $C_0$ 所需要付出的成本，$\cfrac{1}{N}$ 表示選到最小值的機率
* 同理，$\cfrac{C_1+C_{N-2}}{N}$ 中，$C_1+C_{N-2}$ 表示選到第二小值 $C_1$ 所需要付出的成本，$\cfrac{1}{N}$ 表示選到最小值的機率

將上式兩側同 $\times N$ 後可得

$$
NC_N = N(N+1) + 2(C_0+C_1+...+C_{N-1})
$$

且由 $C_N$ 的算法可推得 $C_{N-1}$ 的複雜度如下 :

$$
(N-1)C_{N-1} = (N-1)N + 2(C_0+C_1+...+C_{N-2})
$$

將 $C_N$ 與 $C_{N-1}$ 兩式相減後可得 :

$$
NC_N - (N-1)C_{N-1} = 2N + 2C_{N-1}
$$

整理後可得 :

$$
\cfrac{C_N}{N+1} = \cfrac{C_{N-1}}{N} + \cfrac{2}{{N+1}}
$$

重複以上的式子做遞迴，可將上式化簡為 :

$$
\begin{align}
\cfrac{C_N}{N+1} &= \cfrac{C_{N-1}}{N} + \cfrac{2}{{N+1}}\\
&= \cfrac{C_{N-2}}{N-1} + \frac{2}{N} + \frac{2}{N+1}\\
&= \cfrac{C_{N-3}}{N-2} + \frac{2}{N-1} + \frac{2}{N} + \frac{2}{N+1}\\
&= \frac{2}{3} + \frac{2}{4} + \frac{2}{5} + ... + \frac{2}{N+1}
\end{align}
$$

:::info
為何最後沒有 $\cfrac{2}{1} + \cfrac{2}{2}$ ?
因為拆到最後的 $\cfrac{C_1}{2}$ 表示只剩下一個元素，沒有必要拆解
:::

將上移項後可得 :

$$
\begin{align}
C_N &= 2(N+1)(\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{N+1})\\
&= 2(N+1) \int_3^{N+1}\frac{1}{x}dx\\
&=2(N+1)\ln N
\end{align}
$$

### 2.3 Summary of performance

因為 quick sort 的複雜度會依據所選定的基準值不同而有不同的結果，為了避免基準值選到最大或最小值，在排序前會先打亂 array 的順序。

然而，再沒有隨機打亂的情況下，該如何避免選到極值 ?可以嘗試挑選 3 個數並取其中位數，就可保證不是最大或最小值。