###### tags: `ADA 4.2` `Selection Problem`
# ADA 4.2: Selection Problem 選擇問題 (求第k名)

Textbook Chapter 9.3 - Selection in worst case linear time

## What is Selection Problem?

取一有 $n$ 個 integers 的 $array A$
求輸出 $array A$ 裡第 $k$ 大的數字


## Solution 1: Sorting

藉由將陣列 $A$ 重新由小排到大，要第 $k$ 大就直接取第 $k$ 位置的值

:::info
:warning: 但因為用到排序(sort)，所以其時間複雜度落在 $O(nlogn)$
:::

:::warning
:exclamation: 當 $n>>k$ , sorting 的時間複雜度就會越差越多
:::

如何將時間複雜度再往下調呢?

## Solution 2: Divide-and-Conquer

### 想法

* 設定一個基準點($pivot$)，將原本的陣列依基準點拆成兩半
* 若 $k \le |X_{>}|$，則代表 $k$ 落在 $X_{>}$ 裡的第 $k_{th}$ 位置上
* 若 $k \gt |X_{>}|$，則代表 $k$ 落在 $X_{<}$ 裡的第 $(k-|X_{>}|)_{th}$ 位置上


:::info
:warning: 我們會希望基準點($pivot$)會盡量在中間，因為如果基準點一邊個數太大，若 $k$ 剛好都落在較大的一邊，則最差情況你要拆 $n$ 遍才能找到你要的數值
:::

### 如何找尋中位數？

* 尋找中位數也是另一個 **Selection Problem**，只是 $k$ 為中位數

#### Step 1: Five Men Per Group

* 將 n 個個數的 array 每5個一組，而會分成總共 $\frac{n}{5}$ 組，每組因為數量為 constant (5個)，強制sorting所花費的時間為 constant


#### Step 2: A Median Per Group

* 每組取其中間值(Median)


:::info
:warning: 上圖為取中間值(**黃點**)而所做 sorting 動作，箭頭代表序列由小變大
:::

#### Step 3: Median of Medians

* 從 $\frac{n}{5}$ 組的所有中間值(medians)在做排序取得中間值(median)


:::info
:warning: 上圖將所有medians在做排序在取其中間值(**紅點**)
:::
:::warning
:man-tipping-hand: 在 medians 取得 median 時，若 medians 個數為偶數，通常會取較小的那個值當作 MoM
Reference: Chapter 9.3 p220.第三點
:::

#### Step 4: Partition via MoM

* 在取得MoM後，將此數作為切割點(pivot)，在 $MoM$ 的左邊為小於 $MoM$ 元素的集合 $X_{<}$，右邊則為大於 $MoM$ 元素的集合 $X_{>}$


#### Step 5: Recursion

接著我們就要判斷 $k$ 位於哪個地方，依照上圖會有三種情況
1. $k$ 落於 $X_{>}$ 裡面（其 index 一樣落在 $X_{>}$ 的第 $k_{th}$ 位置上）
2. $k$ 落於 $MoM$ 上（index 應為 $|X_{>}|+1$）
3. $k$ 落於 $X_{<}$ 裡面（其 index 會落在 $X_{<}$ 的第 $(k-|X_{>}|-1)_{th}$ 位置上）

:::info
:warning: 這裡的recursion有牽涉兩個地方
1. 找尋 $MoM$
2. $k$ 落於 $X_{>}$ 或者 $X_{<}$，就要再做一次遞迴拆解一次(直到序列夠小可以直接找到 $k$ 值)
:::

### Divide-and-Conquer for Selection Problem


依序拆解各個時間複雜度
* base case: $\Theta(1)$
* divide groups with size 5: $\Theta(1)$
* median from group i: $\Theta(n)$
* MoM: $T(\frac{n}{5})$
* case divide: $\Theta(n)$
* case 1: $T(|X_{>}|)$
* case 2: $\Theta(1)$
* case 3: $T(|X_{<}|)$

我們希望 $|X_{>}|$、$|X_{<}|$ 的數量盡量不要差距太大(不然 recursive 的次數就越多)
在做 recursion 時可以每次去掉一些元素
以 $k$ 在 $|X_{>}|$、$|X_{<}|$ 的情況每次可剔除 $\frac{n}{5}\div2\times3 = \frac{3}{10}n$
下回要 recursion 的數量就變為 $\frac{7}{10}n$


### Time Complexity

* $T(n)$ = time for running $Selection(X, k)$ with $|X|=n$

$T(n)=\begin{cases}
\Theta(1) &\text{if }n=1\\
T(\frac{n}{5})+max(T(|X_{>}|),T(|X_{<}|))+\Theta(n) &\text{if }n\gt1
\end{cases}$

becomes...

$T(n)=\begin{cases}
\Theta(1) &\text{if }n=1\\
T(\frac{9n}{10})+\Theta(n) &\text{if }n\gt1
\end{cases}$

applying [Master Method](https://hackmd.io/5LI2VRehQWC6AlQYGP99LQ) case 3

$T(n)=\Theta(n)$

applying [Sustitution Method](https://hackmd.io/gmMbJeQ7Q5yMbYnyrk_b6g)


---