# 2024q1 Homework2 (quiz1+2)
contributed by < `164253` >

## 第一周
### 測驗一
#### 原理
用 quick sort 排序，一個 stack 紀錄哪些區間待排序以省略遞迴呼叫，做到類似 dfs 但加上尾遞迴優化的效果。
每次以第一個元素做 pivot 。
#### 延伸問題:優化
首先要避免的是 quick sort 的最差狀況，也就是正好相反排序時，原因是每次分治兩邊不均勻。
因此可以先找到中位數參照[我以前解的一道 leetcode 題目](https://hackmd.io/wX5w04CuTY-T4hosjmfosw?view#2QuickSelect)，用 quick select 並自行實作，以三個元素為一組找出中位數，對這 $\lfloor\frac n3\rfloor$ 個中位數找中位數，並紀錄現在共有多少元素，可以不使用遞迴就實現，最終 $O(n+\frac n3+\frac n9+\cdots)=O(n)$ 求出