3.2.1 - Insertion Sort

1. 演算法

將第$i$筆資料插入到前面$i-1$筆已經排好的資料當中，形成$i$筆排好的資料。

void Insert(char *arr, int index){
    int former = index-1;
    int insert = arr[index];
    while (insert < arr[former]){
        arr[former+1] = arr[former];
        former--;
    }
    arr[former+1] = insert;
}

void Sort(char *arr){
    for (int i = 1; i < strlen(arr); i++)
        Insert(arr, i);
}

演算法解析:

$input = \{5, 3, 8, 2, 6\}$

$i = 1,\ Insert(input,\ 1),\ insert=3\\ while(3<5)\Rightarrow\underline{5,\ 5},\ 8,\ 2,\ 6\\ input[0]=insert\Rightarrow\ \underline{3,\ 5},\ 8,\ 2,\ 6$

$i = 2,\ Insert(input,\ 2),\ insert=8\\ while(8<5)\Rightarrow \times \\ input[2]=insert\Rightarrow\ 3,\ 5,\ \underline{8},\ 2,\ 6$

$i = 3,\ Insert(input,\ 3),\ insert=2\\ while(2<8)\Rightarrow 3,\ 5,\ 8,\ \underline{8},\ 6\quad ,former =1\\ while(2<5)\Rightarrow 3,\ 5,\ \underline{5},\ 8,\ 6\quad ,former =0\\ \\ while(2<3)\Rightarrow 3,\ \underline{3},\ 5,\ 8,\ 6\quad ,former =-1\\ \\ input[0]=insert\Rightarrow\ 2,\ 3,\ 5,\ 8,\ 6$

$i = 4,\ Insert(input,\ 4),\ insert=6\\ while(6<8)\Rightarrow 2,\ 3,\ 5,\ 8,\ \underline{8}\quad ,former =2\\ while(6<5)\Rightarrow\times \\ input[3]=insert\Rightarrow\ 2,\ 3,\ 5,\ 8,\ 6$

2. 性質

• Time Complexity: Best Case O(n)

• Space Complexity: O(1)

Insertion sorting is a stable sorting method.

3. 其他

Insertion sort主要分成兩個步驟，

1. 找到正確的插入位置(linear search)⇒O(n)

2. 將 $n-i$筆資料往後挪動⇒O(n)

所以可以朝這兩個步驟來改善時間效率。

3.1 Binary Insertion Sort

1. 使用Binary Search找到正確位置⇒O(logn)

2. 將 $n-i$筆資料往後挪動⇒O(n)

3.2 Linear Insertion Sort

1. 找到正確的插入位置(linear search)⇒O(n)

2. 改用Linklist來挪動資料⇒O(1)