iT邦幫忙

2021 iThome 鐵人賽

DAY 3
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 3

Day-3 insertion sort與循環不變式

插入排序(insertion sort)

Input: 一連串正整數所成的集合 { https://chart.googleapis.com/chart?cht=tx&chl=a_1%2Ca_2%2C...%2Ca_n }
Output: 一連串已經過排序的正整數集合 { https://chart.googleapis.com/chart?cht=tx&chl=a_1'%2Ca_2'%2C...%2Ca_n' },且https://chart.googleapis.com/chart?cht=tx&chl=a_1'%3C%3Da_2'%3C%3D...%3C%3Da_n'

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

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

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

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

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

輸入的陣列為 https://chart.googleapis.com/chart?cht=tx&chl=A%20%3D%20{https://chart.googleapis.com/chart?cht=tx&chl=%205%2C2%2C4%2C6%2C1%2C3%20}
(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對https://chart.googleapis.com/chart?cht=tx&chl=A%20%3D%20{https://chart.googleapis.com/chart?cht=tx&chl=%2031%2C41%2C59%2C26%2C41%2C58%20}進行升序和降序的排序

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("");
}
  1. 考慮以下搜尋元素的問題
    Input : 由n個正整數所組成的集合https://chart.googleapis.com/chart?cht=tx&chl=A%20%3D%20{ https://chart.googleapis.com/chart?cht=tx&chl=a_1%2Ca_2%2C...%2Ca_n }和一個正整數https://chart.googleapis.com/chart?cht=tx&chl=v
    Output : 輸出一個index i使得https://chart.googleapis.com/chart?cht=tx&chl=v%20%3D%20A%5Bi%5D成立,若https://chart.googleapis.com/chart?cht=tx&chl=v不在https://chart.googleapis.com/chart?cht=tx&chl=A集合中,則回傳https://chart.googleapis.com/chart?cht=tx&chl=NULL
    請以線性搜尋(Linear search)的方式寫出該程式的虛擬碼,遍歷整個陣列來尋找https://chart.googleapis.com/chart?cht=tx&chl=v,並使用循環不變式來證明我們所寫出的演算法正確的。

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


上一篇
Day-2 演算法介紹
下一篇
Day-4 演算法分析概念
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言