Sorting Problem
Input: A sequence of n numbers { \(a_0, a_1, ... , a_{n-1} \)}
Output: A permutation (reordering) { \(a'_0, a'_1, ... , a'_{n-1} \)} of the input sequence such that \( a'_0 \leq a'_1 \leq ... \leq a'_{n-1} \)
Algorithm
An algorithm is a sequence of computational steps that transform the input into the output.
Insertion Sort 概念
Insertion Sort 和打撲克牌時，從牌桌上逐一拿起撲克牌，在手上排序的過程相同。
舉例
Input: {5 2 4 6 1 3}。
首先拿起第一張牌, 手上有 {5}。
拿起第二張牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。
拿起第三張牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。
以此類推。
Insertion Sort 演算法概念
Input: {A[0], A[1], ... ,A[n-1]}
Index j 代表目前要 insert 到手上的牌。
j iterate thru 1 to n-1
在各個 iteration 之前，{A[0], A[1], ... A[j-1]} 是 sorted。
在各個 iteration 完成後，{A[0], A[1], ... A[j-1], A[j]} 是 sorted。
這樣的 algorithm design technique 稱之為 incremental approach (遞增法)。
C++ implementation (in-place sorting)
Performance Analysis
Worst case performance: \( O(n^2) \)
worst case: array 反向排序 (數字由大到小排序)。Average case performance: \( O(n^2) \)
loop 被執行的次數: \( \sum_{j=1}^{n-1} j = \frac{(n-1)*n}{2} \)
running time: \( O(n^2) \)
平均而言，loop 被執行的次數: \( \sum_{j=1}^{n-1} \frac{j}{2} = \frac{(n-1)*n}{2*2} \)Best case performance: \( O(n) \)
running time: \( O(n^2) \)
best case: array 已排序完成 (數字由小到大排序)。Space complexity: \( O(1) \) auxiliary
loop 被執行的次數: \( \sum_{j=1}^{n-1} 1 = n-1 \)
running time: \( O(n) \)
此 in-place 演算法並沒有隨著 array length 額外需要 space, 因此 space complexity 是 \( O(1) \) auxiliary。
延伸閱讀
[書籍] Introduction to Algorithms, 3rd. edition - Chap 2
[WiKi] 插入排序
[WiKi] Insertion sort
系列文章
Insertion Sort (插入排序)
Merge Sort (合併排序)
Heapsort (堆積排序)
