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

## 1. Selection sort
### 1.1 Selection sort demo

> In iteration `i` , find index `min` of smallest remaining entry, Then Swap `a[i]` and `a[min]`

:::info
(1) 每次的迭代會看過整個 Array 並挑選(select)最小的元素
(2) 若 Array size $=n$ 則排序次數依序為 $n \rightarrow n-1 \rightarrow n-2 \rightarrow \cdot\cdot\cdot$
:::

* Initial : `Array, a = [7, 10, 5]` and index `i = 0`
* Index `i = 0` and `a[min] = a[2] = 5`
* Swap `a[0]` and `a[2]`
* Output : `Array = [5, 10, 7]`
* Index `i = 1` and `a[min] = a[2] = 7`
* Swap `a[1]` and `a[2]`
* Output : `Array = [5, 7, 10]`

### 1.2 Analysis
Selection sort 使用了 $(N-1)+(N-2)
+...+1+0 \sim \cfrac{N^2}{2}$ 次的比較(compare)以及 $N$ 次的搬移(exchange)

特色 :
* Running time 與 input size 沒有關係
* 即使是給定已經排序好的陣列，也是需要二次方的時間複雜度
* 資料搬移的量最小(Linear cost)

## 2. Insertion sort
### 2.1 Insertion sort demo
> In ireration `i` , swap `a[i]` with each larger entry to its left

:::info
(1) 從 Array 裡面抽牌(照 index 順序抽)
(2) 抽到某張牌後往左看(已經排好的)並依序比較
(3) 比該張抽到的牌大就互換，尋找最佳的插入位置
:::

* Initial : `Array a = [7, 10, 5, 3]`
* Index : `i = 0` (抽牌)
* Compare : `j = 0` (比較)
* Index : `i = 1`
* Compare : `j = 1`
* `a[j-1] = a[0] < a[j] = a[1]` , 不動
* Index : `i =2`
* Compare : `j = 2`
* `a[j-1] = a[1] > a[j] = a[2]` , 互換
* a = [7, 5, 10, 3]`
* Compare : `j = 1`
* `a[j-1] = a[0] > a[j] = a[1]` , 互換
* `a = [5, 7, 10, 3]`
* Index : `i = 3`
* Compare : `j = 3`
* `a[j-1] = a[2] > a[j] = a[3]` , 互換
* `a = [5, 7, 3, 10]`
* Compare : `j = 2`
* `a[j-1] = a[1] > a[j] = a[2]` , 互換
* `a = [5, 3, 7, 10]`
* Compare : `j = 1`
* `a[j-1] = a[0] > a[j] = a[1]` , 互換
* `a = [3, 5, 7, 10]`

實作上程式碼中會有兩個迴圈，外層遞增迴圈，用來依序牌；內層遞減迴圈，用來依序比較

### 2.2 Analysis
**Best case**
針對本身已經排序(遞增)的陣列，從右側未排序的元素(`a[i]`)依序抽牌時，僅需要與其左邊的元素(`a[i-1]`)比較(compare)一次即可，且不用做任何互換(exchange)，總共只需要比較 $N-1$ 次，複雜度為 $N$

**Worst case**
對遞減排序的陣列，第$N$牌需要比較$N-1$次以及搬運$N-1$次，所以比較次數為 : (搬運同理)

$$
N+(N-1)+...+1= \frac{(N+1) \cdot N}{2} = \frac{1}{2}N^2
$$

**Average case**
直接取 Best case 與 Worse case 的平均 :

$$
(N + \frac{1}{2} N^2) \cdot \frac{1}{2} \sim \frac{1}{4} N^2
$$

## 3. Comparable interface
自己寫的物件，系統預設排序不見得能夠使用，通常只有 `string`、`int`等內建的 data type 可以使用 system sort
> **Question :** 如何將自定義的物件用在 system sort ?
> **Answer :** 需要定義兩個物件如何比大小

### 3.1 Callback
> **Definition.** Callback
> Call = reference a executable code (引用一個可執行的程式)

Callback function 是一種在特定事件或條件發生時才會被呼叫的函式，幾乎所有的程式語言都有支援。可以在指定的時候再呼叫這個函式，且這個函式會被當作參數來傳遞到另一個函數中，如同字面上的名稱 call back(待會叫你)

以排序舉例，當使用系統排序針對自定義物件作排序時，需要先創建一個函式 `comparable()` 來定義如何排序，這個函式就是 callback function (需要排序時才會被呼叫)。當使用系統排序時，系統排序函式又會呼叫 `comparable()` 函式來做比較

其他程式語言的 callback function 支援方式
* C : function pointers
* Python : first-class function(同等函式)


## 4. Shell sort
**Insertion sort 的優點**
* 適合用在較小的資料
* 適用於已經有部分排序好的數據
* Ex : 對排序好的遞增數列(best case)，其複雜度為 $N$

> **Core concept of shell sort**
> 1. 利用 insertion sort 的優點
> 2. 創造一個可以使用 insertion sort 的環境

### 4.1 Shell sort demo

* 選擇一個適當的 $h$ 值
* 兩種理解方式
* 看法(1)
* 每 $h$ 個元素挑出來形成一個小的 Array
* 針對這個小的 Array 做 insertion sort
* 排序完後再使用類似 sliding window 的方式依照 $h$ 值繼續挑選小的 Array 做 insertion sort (下圖紅色與藍色敘述)
* 看法(2)
* 從頭開始第 $i$ 個元素與第 $i+h$ 個元素做比較
* 若 `a[i] > a[i+h]` 則互換(下圖黑色圖示)
* 排序完的 Array 稱為 h-sorted
* 往下挑選較小的 $h$ 值繼續排序
* 當 $h=1$ 時就是傳統的 insertion sort


**shell sort 的精神**
1. 當 $h$ 值較小時，基本上已經快排好，接近線性成本
2. 當 $h$ 值較大時，sub-array 較小，可以使用 insertion sort 排序

:::info
(1) 最佳 $h$ 值目前尚未定論
(2) 如果 $h$ 值選擇 : $1$、$2$、$4$、$8$、...則容易找到重複的狀況，例如 8-sorted與4-sorted會重複做
:::

### 4.2 Analysis
> Shell sort 的 worst-case 是 $N^{1.5}$


由上表可知
* 適當的調整 $h$ 值是可以做到 $N^{1.3}$ 等級的效能
* 當 N 值不是很大(Ex: $N=20,000$)時，Shell sort 是佔有優勢的($N^{1.3}=390\text{k}$)
* 但當 N 值很大(Ex: $N=80,000$)時，shell sort 不見得是最好的($N^{1.3}=2366 \text{k}$)

==當 N 值不是很大時，Shell sort 是個好選擇==

實務上，Shell sort 常被用在許多的**嵌入式系統**中

### 4.3 Summary

h-sequence 的動作可視為 $\log N$ 規模的等級，每個子陣列 h 都要做 n 次，所以 Best case 是 $N \log N$

## 5. Shuffling
### 5.1 How to shuffle an array

> **Goal :**
> Rearrange array so that result is a uniformly random permutation

:::info
雖然是做 shuffle(洗牌)，但本質上還是做一種排序。做法是**隨機**產生一組數字作為排序的**順序**，且元素**排序在每個位置的機率都相同**
:::

### 5.2 Knuth shuffle
> * In iteration $i$ , pick integer $r$ between $0$ and $i$ uniformly at random
> * Swap $a[i]$ and $a[r]$


洗牌過程中，必須從頭到尾把整個 Array 看過一次，所以**複雜度 $=N$**

**Prove : probability is evenly**


:::danger
**問題:question:**

實作上在 randomly pick 階段要如何進行？
:::