泡沫排序法

泡沫排序法 (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)\)。


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