插入排序(insertion sort)

Input: 一連串正整數所成的集合 { }
Output: 一連串已經過排序的正整數集合 { }，且

雖然概念上我們是針對一個序列進行排列，但實務上我們是透過陣列實作。

下面會透過虛擬碼的方式來描述插入排序法，之所以透過虛擬碼進行描述，原因在於使用虛擬碼較容易理解一個演算法的概念，虛擬碼可以不用注意一些語法細節或是些軟體工程的問題，可以讓我們更加專注研究於演算法本身。

插入排序法，在排序的元素不多時十分的有效率。插入排序法的進行方式很像我們在排序手上的撲克牌

首先，所有卡牌目前是牌面向下放在桌上，我們用左手從桌上抽起一張牌，接著拿下一張牌，如果這張牌比原本手上的牌點數還要大時，我們就把這張牌放在原本牌的右邊，如果比較小就放在左邊，如上圖所示。

接著我們將這個過程以虛擬碼的方式寫出來，而這個虛擬碼描述的即是插入排序法了，Input使用陣列A[1...n]表示n個正整數所成的集合，經過演算法將陣列中的元素重新排序後輸出，插入排序法便完成了。

輸入的陣列為 {}
(a) 拿起2這張牌，發現第一張牌比他大，第一張牌往後移動一格，並將2這張牌放入
(b) 拿起4這張牌，發現第二張牌比他大，但第一張牌沒有，第二張牌往後移動一個，並將4這張牌放入
(c) 拿起6這張牌，發現前三張沒有一張牌比他大，因此不做任何動作
(d) 拿起1這張牌，發現前四張皆比他大，前四張都往後移動一格，並將1這張牌放入
(e) 拿起3這張牌，發現三,四,五張皆比他大，因此這三張往後移動一格，將3這張牌放入。
(f) 該陣列已經完成排序。

雖然這樣描述起來我們好像是用兩個陣列進行排序的操作，但實作上我們只使用一個陣列去完成操作，也就是在原地(In-place)完成操作。

虛擬碼:

for j = 2 to A.length
    key = A[j]
    //Insert A[j] into the sorted sequence A[1...j - 1]
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

每一次for迴圈的迭代就是在選擇黑色方塊，也就是比較的對象key，這個key和他左邊的撲克牌點數進行比較，在第6行的地方表示向右移動移動一格，也就是上圖灰色箭頭的部分，第8行，對應到上圖黑色箭頭則表示key要移動到的位置。1到j的部分已經排序完成，剩餘需排序的為j + 1到n。

上面虛擬碼展示了插入排序法是如何運作的. index j表示正準備要放入手中的撲克牌，在外層for迴圈(index為j)的每一輪迭代的開始，包含元素A[1,...,j - 1]的子陣列組成了左手中已經經過排序的手牌，元素A[j + 1,...,n]對應到還在桌上的那些牌。實際上，元素A[1,...,j - 1]是一開始在桌上1到j - 1的那些元素，但現在已經經過排序放在左手了，下面，將以循環不變式(loop invariant)來表示A[1,...,j-1]所具備的性質

驗證演算法的正確性，循環不變式(loop invariant)

循環不變式(loop invariant)本質上就是每一次迭代都會成立的一個條件或是表示式，主要是用來幫助我們理解為什麼一個演算法是正確的. 對於循環不變量，我們需要遵守下面三個法則
:::info
初始化(Initialization) : 在第一次迭代開始之前，應該要是正確的。

維持(Maintenance) : 如果他在某一次迴圈的迭代之前是正確的，那麼他在該迴圈的下一次迭代之前也應該是正確的。

終止(Termination) : 當迴圈停止時，循環不變量會給我們一個性質，這個性質可以用來證明演算法是正確的。
:::

當初始化和維持皆成立時，就能確保循環不變量在迴圈的每一輪迭代開始之前，都是正確的。這裡的推論過程很像數學歸納法，為了證明某一個性質成立，需要證明一個基本情況和歸納步(第k步)，在這裡，證明第一次迭代情況之前循環不變量是正確的為基本情況，證明從某一次迭代到下一次迭代循環不變式正確為歸納步(第k步)。

第三個性質，我們將使用循環不變量來證明第三個性質的正確性(第k + 1步)，通常，我們會將循環不變式和導致迴圈終止的條件一起使用。而這裡的終止性不同於數學歸納法中的做法，這裡只要循環停止時，便停止歸納。

舉例來說:

int j = 9; for(int i=0; i<10; i++) j--; 

初始 : 在第一次迭代以前， i + j == 9成立
維持 : 每一次迭代開始之前，i + j == 9皆成立
終止 : 當迴圈結束後，i + j == 9依然成立

這個例子中，只要i + j == 9，這個循環不變式便成立，可以印證這個迴圈是沒有錯誤的。

下面就嘗試證明插入排序法是正確的演算法

循環不變式 : 每一次迭代從陣列A裡面舉出第j個元素插入到有順序的陣列A[1... j - 1]，然後遞增j。這樣A[1...j - 1]就始終都是排好序的，而我們的循環不變式就是A[1...j - 1]是始終保持排好序的。

• 初始化(Initialization) : 首先證明在第一次迭代之前(在j初始化為2時)，循環不變式成立。子陣列A[1,...,j - 1]僅由單個元素A[1]所組成，實際上就是A[1]中原來的元素，且該子陣列式已經排序完成的，因此，這表示第一次迴圈迭代之前循環不變式成立。

• 維持(Maintenance) : 接著證明每一次迭代維持循環不變式。大概描述一下，for迴圈得主體的第4行到第7行將A[j - 1], A[j - 2], A[j - 3]等元素向右移動一個位置，直到找到A[j]適合放入的位置，第8行將A[j]的值插入到該位置。這時候的子陣列A[1,...,j]是由原來在A[1,...,j]中的元素所組成，但子陣列已經按照順序進行排列。那麼對於下一次for迴圈的迭代，j增加將保持循環不變式。

補充: 其實更精確，更嚴謹的做法應該要去證明while迴圈的循環不變式，但這麼做，便偏離了我們要證明演算法本身，有點太過於鑽牛角尖了，因此一般來說不會那麼做，而是依靠以上大略的分析去證明維持性對於外層迴圈是成立的。

• 終止(Termination) : 最後要來看看循環停止時發生了什麼事情。for迴圈的終止條件為j > A.lenght = n。因為每一次循環迭代j都會增加1，那麼必有j = n + 1(for迴圈的更新值)。在循環不變式的描述中我們將j以n + 1替換掉，可以得到子陣列A[1,...,n]由原來在A[1,...,n]中的元素所組成，但已經按照順序進行排列。這裡我們可以發現，子陣列A[1,...,n]就是整個陣列，我們可以推測出整個陣列已經完成排序，因此這個演算法是正確的。

C語言程式碼

int main(void)
{
    int A[] = {5, 2, 4, 6, 1, 3};
    int len = sizeof(A) / sizeof(int);
    for (int i = 1; i < len; i++)
    {
        int key = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > key)
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
    }
}

for迴圈從i = 1開始

選到A[1](2)這張牌，當作key(比較的標的)，從這張牌的前一張開始進行比較，因此j = i - 1
進入while迴圈開始比較，如果j(1) >= 0且A[j](5) > key(2)，則進行while迴圈內的動作

A[j + 1](2) = A[j](5)，表示把比key大的數字往後移動一格
j--，表示往前一格繼續比較剩餘的卡牌

while整輪的動作就是和key前面的牌進行比較，如果比key還要大，則往後移動一格

A[j + 1] = key，在剛剛j停下的位置後一格放入key。

再來看一個例子，二元搜尋法

int binary_search(int *array, int len, int target)
{
    int start = 0;
    int end = len;
    while(start <= end)
    {
        int mid = (start + end) / 2;
        if(array[mid] == target)
        {
            return mid;
        }
        else if(array[mid] < target)
        {
            start = mid + 1;
        }
        else
        {
            end = mid - 1;
        }
    }
    return -1;
}

這裡的循環不變式，是以下的述句

if array[mid] == target, then start <= mid <= end

如果這個函式回傳了target所在的位置，表示我們有找到目標元素，如果找到目標元素，則目標元素必定在陣列當中。如果迴圈停止，則start <= mid <= end。

練習

1. 使用insertion sort對{}進行升序和降序的排序

Answer: 上方的示範為升序排列，若要降序，則依照以下作法
如果發現key比前面的牌還要大，則前面的牌往前移動，空出空位給key

#include <stdio.h>

void insertion_sort_up(int *, int);
void insertion_sort_down(int *, int);
void print_array(int *, int);

int main(void)
{
    void (*func[3])(int *, int) = {insertion_sort_up, insertion_sort_down, print_array};
    int A[] = {31, 41, 59, 26, 41, 58};
    int len = sizeof(A) / sizeof(int);
    func[0](A, len);
    func[2](A, len);
    func[1](A, len);
    func[2](A, len);


}

void insertion_sort_up(int *A, int len)
{
    for(int i = 1; i < len; i++)
    {
        int key = A[i];
        int j = i - 1;
        while(j >= 0 && key < A[j])
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
    }
}

void insertion_sort_down(int *A, int len)
{
    for(int i = 1; i < len; i++)
    {
        int key = A[i];
        int j = i - 1;
        while(j >= 0 && key > A[j])
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
    }
}

void print_array(int *A,  int len)
{
    for(int i = 0; i < len ; i++)
    {
        printf("%d ", *(A + i));
    }
    puts("");
}

2. 考慮以下搜尋元素的問題
   Input : 由n個正整數所組成的集合{ }和一個正整數。
   Output : 輸出一個index i使得成立，若不在集合中，則回傳。
   請以線性搜尋(Linear search)的方式寫出該程式的虛擬碼，遍歷整個陣列來尋找，並使用循環不變式來證明我們所寫出的演算法正確的。

Answer:

LINEAR-SEARCH(A, v)
    for i = 1 to A.length
       if A[i] == v
            return i
    return NIL

循環不變式 : 在每一次for迴圈的迭代開始之前，子陣列A[1,...,i - 1]由與v不同的元素所組成。

初始化(Initialization) : 在第一次迭代開始之前，子陣列為一個空陣列(空集合)，由與v不同的元素所組成。

維持(Maintenance) : 在每一次迭代，我們將v和A[i]進行比較，如果在A中找到v，則我們會回傳index i。如果不等於，我們就繼續進行下一次迭代。若在最後一次迭代中沒有在A中找到v，則表示v並不在A裡面，循環不變式，子陣列A[1,...,i - 1]由與v不同的元素所組成這件事情依然成立。

終止(Termination) : 迴圈終止條件為當i > a.length = n. 每當i + 1時，我們必須讓i = n + 1同時發生，將循環不變式中子陣列A[1,...,i - 1]中的i以n + 1代換掉，得到A[1,...,n]，且這個子陣列是由不同於v的元素所構成的，也因此會回傳NIL。
到這裡，我們證明迭代結束時，子陣列A[1,...,i - 1]由與v不同的元素所組成，因此演算法正確。

參考資料: Introduction to algorithms 3rd