資料結構與演算法—插入排序 Insertion Sort

筆記頁面：資料結構與演算法

Pseudo Code

INSERTION-SORT(A,n)
1for i = 2 to n
2    key= A [i]
3    // Insert A[i] into the sorted subarray A[1:i-1]
4    j = i - 1
5    while j > 0 and A[j] > key
6        A[j + 1] = A[j]
7        j = j - 1
8    A[j + 1] = key

時間複雜度分析

line	cost	times
1	$c_1$	$n$
2	$c_2$	$n-1$
3	$c_3$	$n-1$
4	$c_4$	$n-1$
5	$c_5$	$\sum _{i=2}^n{t}_i$
6	$c_6$	$\sum _{i=2}^n(t_i-1)$
7	$c_7$	$\sum _{i=2}^n(t_i-1)$
8	$c_8$	$n-1$

$$\begin{array}{c}T(n)=c_{1}n+c_2(n-1)+c_3(n-1)+c_4(n-1)+\hfill \\ \hfill c_5\sum _{i=2}^n{t}_i+c_6\sum _{i=2}^n(t_i-1)+c_7\sum _{i=2}^n(t_i-1)+c_8(n-1)\end{array}$$

Best Case

the best case occurs when the array is already sorted
line 5-7 will never be executed

$$\begin{array}{rl}\Rightarrow T(n)& =(c_1+c_2+c_3+c_4+c_8)n-(c_2+c_3+c_4+c_8)\\ leta& =c_1+c_2+c_3+c_4+c_8\\ letb& =c_2+c_3+c_4+c_8\\ \Rightarrow T(n)& =an-b\end{array}$$

最佳情況所消耗之時間為線性增長的

$O(n)$

Worst Case

最糟情況是每一次的排序，都要把要插入的值移到第一個位置。也就是說 5-7 行都會跑滿，使得

$t_i=i$。因此我們可以將 Summation 的式子化簡：

$$\begin{array}{rl}\sum _{i=2}^n{t}_i=\sum _{i=2}^{n}i=(\sum _{i=1}^{n}i)-1=& \frac{n(n+1)}{2}-1\\ \sum _{i=2}^n(t_i-1)=\sum _{i=2}^n(i-1)=\sum _{i=1}^{n-1}i=\frac{(n-1)(n-1+1)}{2}=& \frac{n(n-1)}{2}\end{array}$$

在將化簡後的式子帶入原式：

$$\begin{array}{rl}\Rightarrow T(n)=& c_{1}n+c_2(n-1)+c_3(n-1)+c_4(n-1)+\\ & c_5(\frac{n(n+1)}{2}-1)+c_6(\frac{n(n-1)}{2})+c_7(\frac{n(n-1)}{2})+c_8(n-1)\\ =& (\frac{c_5}{2}+\frac{c_6}{2}+\frac{c_7}{2})n^2+(c_1+c_2+c_3+c_4+\frac{c_5}{2}-\frac{c_6}{2}-\frac{c_7}{2}+c_8)n\\ & -(c_2+c_4+c_5+c_8)\\ leta=& \frac{c_5}{2}+\frac{c_6}{2}+\frac{c_7}{2}\\ letb=& c_1+c_2+c_3+c_4+\frac{c_5}{2}-\frac{c_6}{2}-\frac{c_7}{2}+c_8\\ letc=& c_2+c_4+c_5+c_8\\ \Rightarrow T(n)=& a{n}^2+bn-c\end{array}$$

最糟情況所消耗之時間為指數增長的

$O(n^2)$

C Code

void Insert_Sort(int *arr, int len) {
    
    // i is point to value to insert
	for(int i = 1; i < len; i++) {
		int item = arr[i];
		
		// shift back when sorted value is large than item
		int j = i - 1;
		for(; j >= 0 && arr[j] > item; j--) {
			arr[j+1] = arr[j];
		}
        
		// insert into empty position
		arr[j+1] = item;
	}
}