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

前言

第六天我們終於開始上主菜了，第一個演算法Brute Force中的Selection Sort（複習連結在此)，稍微複習一下，Selection Sort的邏輯是從一組數列中找出最小的值，然後與位在數列最前面的數值交換，直到整個數列都跑過了一輪，數列的順序也就成了從小至大的排序結果，而Selection Sort的時間複雜度(Time complexity)是Ｏ(n^2)。

今天我們要來上第二道蔡，同樣是屬於Brute Force中的Bubble Sort。

佐料 - Stable Sorting

在講Sorting的時候，其實還有一個小小觀念可以帶出來，就是Stable Sorting。

Stable Sorting並不是一種演算法，它是附加於Sorting相關的方法(演算法)的一種概念，如果Sorting後的結果針對重複Key的資料保留了原先的順序時，則這個Sorting方法（演算法）就可被稱為Stable Sorting。讓我們看看下面的範例：

從上圖可以看到，在使用數字做為排序所使用的Key時，排序前與排序後，同樣Key的值的順序是一樣的，可以符合這種效果的排序就稱為Stable Sorting。

那昨天介紹的Selection Sort是屬於Stable Sorting嗎？ 大家可以想想，解答會在今日小結中公布。

Bubble Sort如何運作？

Bubble Sort在排序的演算法中也算是經典了，而且也是很容易了解的演算法之一；和Selection Sort有一點類似，都是比較和交換，只是Selection Sort是先把資料全部比較完再交換，而Bubble Sort是邊比較邊交換，具體步驟如下：

1. 將數列中第一與第二的數值進行比較，若第一個數值大於第二個數值，兩者交換位置；再來，將第二與第三的數值進行比較，若第二個數值大於第三個數值，再交換，反之，則維持原狀；基於這樣的方式，最大的數值將會被『交換』到最後一個位置。
2. 重複上述步驟，只是這次會將第二大的數值會被交換到 『倒數第二』個位置。
3. 再重複上述步驟，直到整個數列排序完畢。

所以，與Selection Sort不同，Selection Sort是找出最小值來移動，而Bubble Sort是針對最大值做移動。讓我們來看看Pseudo-Code大概是怎麼實作Bubble Sort：

// Input: An array Array[0...n-1] of orderable elements
// Output: An array Array[0...n-1] sorted in ascending order
function BubbleSort(Array[0, ..., n-1]){
    for i = 0 to n-2 {
        for j = 0 to n-2-i {
            if Array[j+1] < Array[j]{
                SWAP Array[j] and Array[j+1]
            }
        }
    } 
}

內層迴圈的限制之所以除了減2後再減i，是因為Bubble Sort每跑完一次外層迴圈，最後的目標位置會往前移一個。

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

同樣的，再講Bubble Sort之前，我們再來看一下Bubble Sort的動圖流程吧，希望這樣可以幫助到大家更容易理解Bubble Sort的執行過程：

會有人看完這個GIF後覺得，在排完4的位置時，整個數列基本上已經是排序完畢了，為什麼之後還是繼續進行比較嗎？（我一開始有這樣想過ＸＤ）原因是因為程式『看不到』數列當下已經排序完了，所以對程式而言，他會繼續執行下去。而跟Selection Sort一樣，Bubble Sort在執行過程中總共比較了28次，但是卻也交換了18次，整整比Selection Sort多了一倍多，也因為Bubble Sort在實作時同樣要跑一個雙層迴圈，因此Bubble Sort的時間複雜度為?(n^2)；而Bubble Sort的Best Case、Average Case和Worst Case會發生在下列狀況：

1. Best Case是發生在這一組數列已經是正序排列了，此時數值比較的次數為n^2/2，但交換的次數為0。
2. Average Case則是數列是隨機亂序，此時數值比較的次數為n^2/2，而交換的次數會小於n^2/2。
3. Worst Case則是數列為倒序排列，此時數值比較的次數為n^2/2，而交換的次數亦為n^2/2。

如何提早結束Bubble Sort？

正如同上面範例中，明明在排完4的位置時，整個數列已經完成排序了，那有沒有什麼辦法可以就這樣結束程式的進行呢？答案是有的，這個做法叫做Early-Termination Bubble Sort（提早終止的Bubble Sort），做法其實很簡單：

假設在某一次的iteration當中，完全沒有進行『交換』的動作時，就表示整個數列已經完成排序，而程式就跳出迴圈，結束後續排序的進行。

雖然這樣的做法並不會改變Bubble Sort的時間複雜度，但還是有機會減少整體的執行時間。

小結

• Stable Sorting的定義就是在面對有相同Key的排序，數列排序前後有同樣Key的值的順序維持一致。
• Selection Sort和Bubble都是Stable Sorting。
• Bubble Sort的時間複雜度為Ｏ(n^2)。
• Early-Termination Bubble Sort是可行的。

預告

明天我們將會介紹第三個屬於Brute Force的演算法-knapsack。

References

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