[Algo] 2.2 Analyzing algorithms

我們探討一個演算法的複雜度時，常常只看他的worst case，為什麼呢？
1) 它是upper bound
2) 對有些演算法而言，worst case發生的機率還滿高的
3) 常常average case跟worst case一樣糟

[Algo] 2.1 Insertion sort

Rationale
Insertion sort 就像在整理撲克牌一樣，想像A[1 ... j - 1]是一個已經由小到大排序好的array，而A[j]是一個等待插入排序的element，我們把他稱為key。

排序的方法就是從A[j - 1]這個element開始跟key作比較，如果key比A[j - 1]小的話，那接下來就繼續跟A[j - 2]作比較，以此類推，直到這個key找到他適當的位置在插入為止。如此一來，A[1 ... j]就會變成一個新的且排序好的array。下一步，就可以再從A[j + 1]當作另外一個新的key開始，插入到A[1 ... j]裡面。這樣，就可以把A這個array作完排序的動作。

把key插入到一個排序好的array裡面，這個insertion的動作，就是insertion sort的核心精神。

Pseudocode
@{
\proc{Insertion-Sort}(A)
\li \For j \leftarrow 2 \;\textbf{to}\;\textup{length}[A]
\li \;\;\;\;\textup{key} = A[j]
\li \;\;\;\;\textup{// Insert A[j] into the sorted sequence}\;A[1..j-1]
\li \;\;\;\;i = j - 1
\li \;\;\;\;\While i > 0 \;\textup{and}\; A[i] > key
\li \;\;\;\;\;\;\;\;A[i + 1] = A[i]
\li \;\;\;\;\;\;\;\;i = i - 1
\li \;\;\;\;A[i + 1] = key
}@