3月 07, 2010

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

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



  假設現在我們需要將 n 筆資料 A1、A2、......、An 由小排到大。

  一開始,我們需要先比較 A1 與 A2 兩筆資料的大小。若是 A1 > A2,則交換兩筆資料;接著比較 A2 與 A3。若是 A2 > A3,則交換兩筆資料;以此類推,一直到比較完 An - 1 與 An 為止。



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

  接下來,重複剛剛的動作:比較 A1 與 A2、A2 與 A3、A3 與 A4、......,不同的是,這一次只需要比較到 An - 2 與 An - 1 即可。到目前為止,我們可以確定 An - 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 = (3n2 - n) / 2 ∈ Ο(n2),為一個平方時間(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 = n2 ∈ Ο(n2)。複雜度依舊為平方時間。

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


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

3 回覆:

pojan 提到...

第二段有點怪怪的,應該是A1>A2,兩筆資料才要交換吧?如果是由小到大排序的話

Unknown 提到...

確實是我寫錯了, 感謝您的指正:)

Unknown 提到...

3qq

張貼留言