# Ch7: Quicksort
本章節要介紹的 **Quicksort** 是一種非常實用的演算法，也是現今大多數程式語言內建排序函式所採用的演算法。雖然最壞情形是 $\Theta (n^2)$，但平均來說它的表現非常優異，並且可以原地排序，是許多實際系統中排序的首選。

## 7-1 Description
- **基本流程**：
- 選定一個 **pivot**
- 分成 **high side（通常在右邊）** 與 **low side（通常在左邊）**
- 比 pivot **小**的元素放在 low side
- 比 pivot **大**的元素放在 high side
- 之後在左右遞迴繼續 quicksort

## 7-2 Performance
- **時間複雜度**：
- **最壞情形**：$\Theta(n^2)$，發生在每次 pivot 都選到最小或最大元素
- **平均狀況**：$\Theta(n \log n)$
- 空間複雜度：$O(1)$，因為是原地排序，空間使用效率高

## 7-3 A Randomized Version of Quicksort
- 每次呼叫時**隨機選取**一個當 pivot，能平均分配陣列、避免最壞情況。

## 7-4 Analysis
- 使用**期望值分析法（Expected Value Analysis）** 分析執行時間