泡沫排序法

泡沫排序法 (Bubble Sort) 是一種利用氣泡往上面浮的概念所發明出來的排序方法。 不同大小的氣泡就像是會跟隔壁的人說「借過」一樣，利用不斷交換相鄰兩個元素來達到排序的效果。

假設我們有 $n$ 筆資料。如果我們要實作泡沫排序法，我們可以重複掃描這個陣列，只要發現相鄰兩個數字的大小順序是錯誤的，便交換兩者。 一旦發覺陣列已排好序，就可以停止作業了。寫成程式碼長得像下面這樣：

// 泡沫排序法，呼叫完畢後 arr[] 內的元素將由小至大排列。
void BubbleSort(data_t arr[], int n) {
  while (AlreadySorted(arr, n) == false) {
    // 率先檢查陣列是否已排序。
    for (int i = 0; i + 1 < n; i++) // (1)
      if (arr[i] > arr[i + 1])      // (2)
        swap(arr[i], arr[i + 1]);   // (3)
  }
}

實作上我們也可以利用一個 flag，紀錄在 while 迴圈中發生的事情：如果沒有任何交換的情事發生，則代表它已經排好序了。

正確性的證明

要怎麼證明呼叫 BubbleSort 以後，演算法能夠正確地將 arr[] 裡面的資料排好順序呢？ 很顯然，當程式停下來的時候，AlreadySorted 會回傳 true，因此資料一定是排好順序的。 這是一個賴皮的證明方法，但它是對的。這也是為什麼在上述演算法我們用的是 while 而不是另一層 for-loop。 （但其實需要的核心證明是一樣的） 要怎麼證明演算法一定會停下來呢？這點我們可以留給時間複雜度一併分析。

時間複雜度

我們可以利用數學歸納法證明以下敘述：

引理 1

第 $k$ 次執行 for-loop 之後，最大的 $k$ 個元素已被正確地排入 arr[n-k]...arr[n-1]。

證明

• Base Case: 當 $k=0$ 的時候，我們不需要去排序。
• Inductive Case: 當 $k\ge 1$ 的時候，由於 arr[n-k+1]...arr[n-1] 都被放在正確的位置上，因此我們只要證明： arr[0]...arr[n-k] 當中最大的一筆資料會被置換到 arr[n-k] 的位置即可。怎麼證明這個敘述呢？注意到 for 迴圈 (1-3) 處的部分，假設最大的一筆資料目前在 arr[j]，而我們不妨假設 arr[j] 是所有相同值最右邊的那個。此時，因為 $arr[j] \ge arr[j-1]$，因此 $i=j-1$ 的時候，(2) 不成立。此外，因為 $arr[j] > arr[j+1], \ldots, arr[n-k]$，因此往後的每一次都會觸發 (3) 的交換操作，進而結論成立： arr[j] 被放在該放的位置上。

如果輸入的資料已經排好順序了，那麼泡沫排序便只花費 $O(n)$ 時間檢查陣列是否已排序。 根據引理 1，我們知道 while 迴圈只需要跑 $O(n)$ 次。因此整體泡沫排序法的時間複雜度是 $O(n^2)$。

這樣的時間複雜度分析真的是緊的嗎？是否真的有這麼差的情況發生？