# Insertion Sort
## 示意圖
## pseudocode

### 輸入:A代表要排序的陣列，n則為陣列的長度，陣列從1到n
### 輸出:把A排好的結果(由小到大)

A[i]是這回合要排序的元素，也就是說，經過這回合後，A[1]~A[i]要是排序好的狀態。
### 第1行:
<details>
<summary>問題:為什麼迴圈不是從1到n</summary>
因為在i=1，也就是只有一個元素時，它不用排就排好了。
</details>

### 第2行:
<details>
<summary>問題:為什麼要多用一個變數key，而不是直接用A[i]來排序就好，這樣會多浪費一個變數的空間</summary>
據說是因為陣列有random access的特性，存取陣列的某元素會比存取變數還要慢，所以才把A[i]先存到key裡面，讓程式稍微變快，但細節我並不是很清楚
</details>

### 第4行:
<details>
<summary>問題:j變數的用途，以及為何它的初始值是i - 1</summary>
j變數用來跟key比較，目的是在A中找到比key小的最大值，找到後放在它的右邊(第8行)，也因此A[j+1]一定是空格，或是說當while結束，A[j+1]是放key進去的位置。
</details>

### 第6行:
<details>
<summary>問題:這行要幹嘛</summary>
此時的A[j]仍然大於key，所以把它往右搬一格，讓A[j+1]永遠是空格
</details>

### 可以去網路上查insertion sort的動畫，會更明白它的原理。

## 證明演算法的正確性-loop invariant

見以上程式碼，A[1 , i-1]永遠是sorted(由小到大)，理由如下:
1. **init**: 當i = 1，1 ~ 0 沒有元素，也可以說它們是sorted。
2. **maintenance**: while迴圈會把key插到合適的位置，不會破壞排序的情況，A[1 , i] 是sorted，當i++後，A[1 , i-1]還是為sorted，maintenance成立。
3. **termination**: 當i = n+1，A[1 , i-1]即為A[1 , n]，為sorted(從1跟2推來，類似數學歸納法)，因此迴圈結束時，A[1 , n]就排序好了。

以上三點，證明了此algorithm是正確的。

## Exercises
### 2.1-1 排序<31,41,59,26,41,58>
以下的i都是在迴圈外
i=2:31 41 59 26 41 58
i=3:31 41 59 26 41 56
i=4:31 41 59 26 41 56
i=5:26 31 41 59 41 56
i=6:26 31 41 41 59 56
i=7:26 31 41 41 56 59
### 2.1-2 寫出insertion sort由大到小的版本:

for i = 2 to n:
    key = A[i]
    j = i - 1
    while j > 0 and A[j] < key:
        A[j + 1] = A[j]
        j--
    A[j + 1] = key

### 2.1-3 寫出線性搜尋的pseudocode，並且用loop invariant證明它是對的:
輸入:A = <a1,a2,...,an> and v(要找的數)
輸出:v在A中的索引值，如果找不到，輸出NIL

for i = 1 to n:
    if(A[i] = v) return i
return NIL

設A[1 ~ i-1]中沒有v
1. **init**: 當i = 1，1 ~ 0 沒有元素，確實沒有v。
2. **maintenance**: 如果A[i]是v，就會回傳i，程式結束；如果A[i]不是v，那i+1後，A[1 ~ i-1]中還是沒有v
3. **termination**: 當i = n+1，1 ~ i-1即為1 ~ n，仍然沒有v，因此迴圈結束時，A[1 , n]不存在v，因此return NIL。

### 2.1-4 設計一個演算法，將兩個n-bit的二進制整數相加，二進制整數存在n-element arrays A and B，並且定義輸入輸出:
輸入: A B(二進制整數)，用陣列表示
輸出: C(二進制整數)，用陣列表示，其中，C = A + B

C = {}
//carry是 A[i + 1 , n - 1] + B[i + 1 , n - 1]是否有進位
carry = 0
for i = n - 1 to 0:
    sum = carry + A[i] + B[i]
    carry = sum / 2
    C[i + 1] = sum % 2
C[0] = carry
return C

## Insertion Sort的時間複雜度
algorithm的time complexity為:
**第1行複雜度x(第2行 + 第3行 + 第4行 + ... + 第8行)**
第2行:$O(1)$
第3行:註解
第4行:$O(1)$
第5~7行:看情況
best case為$O(1)$
(A[j] <= key or j <= 0，也就是A[i - 1] <= A[i]，亦即陣列是由小到大的，不用排序)
worst case為$O(n)$
(A[j]一直大於key，直到j <= 0，也就是說，key是最小的，亦即陣列是由大到小的，要一直排)
第8行:$O(1)$

而第1行的time complexity為O(n)，所以此algorithm的複雜度
best case: $\Omega(n)$
worst case: $O(n^2)$

## Exercises
### 2.2-1 $n^3/1000 - 100n^2 - 100n + 3 用\theta表示$
$\theta(n^3)$(將常數忽略，取最大的項)
### 2.2-2 寫出selection sort(由小到大)的pseudocode並且驗證它的正確性、best case 以及worst case的時間複雜度，並且解釋為何外層迴圈只須執行n-1次

for i = 1 to n - 1:
    minIdx = i
    for j = i + 1 to n:
        if(A[j] < A[minIdx])
            minIdx = j
    swap(A[i] , A[minIdx])

設A[1 , i - 1] is sorted, A[i , n]的任一元素一定比A[1 , i - 1]的任一元素大
1. **init**:A[1,0]沒有元素，視為排序好的，因此假設成立。
2. **maintenance**:minIdx是A[i , n]中最小的索引，將A[i]與A[minIdx]交換，A[1 , i] is sorted(原本A[1 , i - 1]就排序好了，而現在A[i]會比A[i-1]大，但比A[i + 1 , n]的任一元素小，所以A[1 , i] is sorted且A[i + 1 , n]會比A[1 , i]大)，當i++後，假設仍然成立。
3. **termination**:當i = n，迴圈中止，A[1 , n - 1] is sorted，A[n]會比A[1 , n - 1]的任一元素大，因此A[1 , n] is sorted.

根據loop invariant，insertion sort確實能將A[1 , n]排序好(由小到大)
而外層迴圈只須執行n-1次，見loop invariant的termination
**time complexity:**
$\theta(n^2)$
(不管怎樣，j的那個迴圈總是要執行n - i次)
### 2.2-3 假設輸入一個n長度的array，每個元素是target的機率一樣，linear search的average case是多少?worst case呢?以及如何用$\theta$表示linear search的average case與worst case
average case: (1 + 2 + ... + n) / n = (n + 1) / 2 $\in$ $\theta(n)$
worst case: n $\in$ $\theta(n)$

### 2.2-4 如何讓幾乎每個演算法都是best case
根據題目要求，調整test case(比如說insertion sort，只要測資是排序好的，它就是best case)