Table of Contents
前言
第六天我們終於開始上主菜了，第一個演算法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是邊比較邊交換，具體步驟如下：
- 將數列中第一與第二的數值進行比較，若第一個數值大於第二個數值，兩者交換位置；再來，將第二與第三的數值進行比較，若第二個數值大於第三個數值，再交換，反之，則維持原狀；基於這樣的方式，最大的數值將會被『交換』到最後一個位置。
- 重複上述步驟，只是這次會將第二大的數值會被交換到 『倒數第二』個位置。
- 再重複上述步驟，直到整個數列排序完畢。
所以，與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會發生在下列狀況：
- Best Case是發生在這一組數列已經是正序排列了，此時數值比較的次數為
n^2/2，但交換的次數為0。 - Average Case則是數列是隨機亂序，此時數值比較的次數為
n^2/2，而交換的次數會小於n^2/2。 - 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。