【演算】氣泡排序法 - Bubble Sort

　　氣泡排序法（bubble sort）是排序演算法（sorting algorithm）中較簡易的一種。其運作的原理是藉由逐次比較相鄰的兩筆資料，並依照排序條件（由大至小或由小至大）交換資料直到排序完成為止。



　　假設現在我們需要將 n 筆資料 A₁、A₂、......、A_n 由小排到大。

　　一開始，我們需要先比較 A₁ 與 A₂ 兩筆資料的大小。若是 A₁ > A₂，則交換兩筆資料；接著比較 A₂ 與 A₃。若是 A₂ > A₃，則交換兩筆資料；以此類推，一直到比較完 A_{n - 1} 與 A_n 為止。



　　這樣就完了嗎？當然還沒。到目前為止，我們只確定 A_n 是 n 筆資料中最大的數字。

　　接下來，重複剛剛的動作：比較 A₁ 與 A₂、A₂ 與 A₃、A₃ 與 A₄、......，不同的是，這一次只需要比較到 A_{n - 2} 與 A_{n - 1} 即可。到目前為止，我們可以確定 A_{n - 1} 是 n 筆資料中次大的數字。

　　接著就繼續重複同樣的動作，便能確定每一輪比較中的最大資料，皆在這些資料的最後面。直到所有資料排序完成為止。



　　其原理的虛擬碼大致如下：

Function bubbleSort(Type data[1..n])
    Index i, j;
    For i from n to 2 do
        For j from 1 to i - 1 do
            If data[j] > data[j + 1] then
                Exchange data[j] and data[j + 1]
End

　　讓我們舉個實際的例子來說明。若是我們現在要將以下這些資料由大排到小：

1 43 6 79 50 2

　　則第一輪的比較與交換過程如下：

43 1 6 79 50 2

43 6 1 79 50 2

43 6 79 1 50 2

43 6 79 50 1 2

43 6 79 50 2 1

　　第二輪的比較與交換過程如下：

43 6 79 50 2 1

43 79 6 50 2 1

43 79 50 6 2 1

43 79 50 6 2 1

　　接下來以此類推。

　　由此可以看到，資料中較小的一筆會藉由交換慢慢「浮」到資料頂端，其「氣泡排序」之名也是因此而來。



　　若是我們分析在最差情況下（即所有資料的順序剛好完全相反，因為我們必須在每一輪迴圈，藉由不斷交換兩筆資料的動作，把最前頭的資料移到最後面），使用氣泡排序法將 n 筆資料排序的敘述執行次數（註1）：

Function bubbleSort(Type data[1..n])
    Index i, j;                                     // 1
    For i from n to 2 do                            // n - 1
        For j from 1 to i - 1 do                    // n(n - 1) / 2
            If data[j] > data[j + 1] then           // n(n - 1) / 2
                Exchange data[j] and data[j + 1]    // n(n - 1) / 2
End

　　可得出所有敘述的執行次數總和為：W(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 = (3n² - n) / 2 ∈ Ο(n²)，為一個平方時間（quadratic time）的演算法。



　　而在最好的情況下（即所有資料都為已排序狀態，因為不需要進行任何一次交換動作）：

Function bubbleSort(Type data[1..n])
    Index i, j;                                     // 1
    For i from n to 2 do                            // n - 1
        For j from 1 to i - 1 do                    // n(n - 1) / 2
            If data[j] > data[j + 1] then           // n(n - 1) / 2
                Exchange data[j] and data[j + 1]    // 0
End

　　所有敘述的執行次數總和為：B(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + 0 = n² ∈ Ο(n²)。複雜度依舊為平方時間。

　　對於一種排序演算法而言，這樣複雜度是相當沒有效率的。因此這個方法多半只是被拿來簡單的解釋排序概念，而不是拿來實際應用。

註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。