本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

第六天到第九天，我們都是在介紹屬於Brute Force的演算法，若要複習的人可以點下面連結：

• 【舌尖上的演算法】Day6 -- Brute Force - Selection Sort
• 【舌尖上的演算法】Day7 -- Brute Force - Bubble Sort
• 【舌尖上的演算法】Day8 -- Brute Force - Knapsack
• 【舌尖上的演算法】Day9 -- Brute Force - DFS & BFS

今天開始的三天，我們就要來介紹另一個演算法類別Decrease and Conquer以及三種屬於這個類別的演算法。

Decrease and Conquer

Decrease and Conquer的中文翻譯成『減治法』，這個名稱我一看到就是滿頭問號，但是當我瞭解他的流程之後，我才恍然大悟，我們在生活中很多事情都是透過這樣的方式在處理問題，只是從來沒想到居然真的被歸納出一個名稱來表示，那到底Decrease and Conquer是怎樣的一個過程呢？簡單來說，它分成下列三個步驟：

1. 將一個大問題拆解成多個小問題
2. 解決這些小問題
3. 將解決這些小問題的方法衍生到原本的大問題

我相信如果大家仔細想想，應該多多少少可以想到一到兩個例子是用這個方式來解決問題的，那到底又有哪些演算法是屬於這種將大問題拆解成小問題來解決的呢？

我們在這三天將會介紹三種：Insertion Sort, Shell Sort和Binary Search，今天我們就來介紹第一種Insertion Sort。

Insertion Sort是什麼？

Insertion Sort其實有一個生活化的例子，大家應該都有玩過撲克牌吧，我們在玩撲克牌很多人都會有個習慣，會把撲克牌一張一張的抽出來，看看這張牌的大小應該在手排中的哪個位置，找到他所屬的位置之後，再插進手牌中，最後手上的牌就是經過排序的樣子，比較方便之後出牌或自己比較容易理解牌型。

其實這個動作就是Insertion Sort，Insertion Sort的步驟就是：

1. 一次考慮一個項目
2. 將這個項目放進(插入)其在已經被考慮過的組合中對應的位置。

我們在玩撲克牌的時候也是這樣去排手牌的吧。

Insertion Sort也算是很容易實現的演算法，其Pseudo-code如下：

// Input: An array Array[0...n-1] of orderable elements
// Output: An array Array[0...n-1] sorted in ascending order
function InsertionSort(Array[0, ..., n-1]){
    for i = 1 to n-1 {
        v = Array[i]
        j = i - 1
        while j >= 0 and Array[j] > v {
            Array[j+1] = Array[j]
            j = j - 1
        }
        A[j+1] = v
    }
}

Insertion Sort的時間複雜度(Time complexity)

按照慣例，讓我們來看個ＧＩＦ圖檔吧：

我的ＧＩＦ圖中省略了一個一個值『換位置』的過程，但仍可從中發現，在一個一個『取值』時，是從左至右取值，但是在進行『比較』的時候，卻是從右至左比較，比較的過程中，當遇到比自己小的值的時候，就會將值放入當前位置；此外，由於Insertion Sort在執行時，也是一個巢狀迴圈的結構，因此其時間複雜度亦為Ｏ(n^2)，而其Best Case、Average Case和Worst Case會發生在下列狀況：

1. Best Case：數列已經排序完畢（正序排列），此時的時間複雜度為Ｏ(n)(因為內層迴圈不會跑，僅跑了外層迴圈而已)。
2. Average Case：數列是隨機排序的狀態且期望每個數值在比較至『一半』的位置時，即可找到對應的位置，此時的時間複雜度為Ｏ(n^2)。
3. Worst Case：數列是反序排列，此時的時間複雜度為Ｏ(n^2)。

小結

• Decrease and Conquer就是把問題變小去解決，再衍生到大問題中。
• Insertion Sort就是玩撲克牌時的排序原理。
• Insertion Sort的時間複雜度為Ｏ(n^2)，但其Best Case的時間複雜度為Ｏ(n)。

預告

明天我們將會介紹的是Insertion Sort的改良版 - Shell Sort。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin