泡沫排序 - Bubble Sort

泡沫排序原理

泡沫排序是一種穩定排序演算法，不斷重複比較兩個元素，如果要最小的開頭，若前一個元素小於現在這個元素，則兩個元素位置互換，反之亦然，直到所有元素都是由小到大排序才結束。而也因為這種『小元素經由交換慢慢浮至集合頂端』，故稱作泡沫排序。

圖片來源

泡沫排序運作

若有一筆資料要從小排到大，使用泡沫排序的步驟如下：

1. 比較相鄰兩個元素，若第一個元素大於第二元素，則兩個位置互換。
2. 針對每個元素（第二與第三…），不斷重複上一步驟，直到最後一個元素。
3. 重複步驟 1, 2 直到資料全部由小到大排序。

可以用[8, 3, 5, 6, 1]來看看：

[8, 3, 5, 6, 1]
 ^  ^
(8 > 3) 兩個位子交換

[3, 8, 5, 6, 1]
    ^  ^
(8 > 5) 兩個位子交換

[3, 5, 8, 6, 1]
       ^  ^
(8 > 6) 兩個位子交換
 
[3, 5, 6, 8, 1]
          ^  ^
(8 > 1) 兩個位子交換

[3, 5, 6, 1, 8]

這樣比一輪，就把最大值給放到最後了。接著就是不段重複上述步驟，直到排序完成。

泡沫排序的時間複雜度（Time complexity）

這是我們剛剛看到的流程，這次加入一個比較次數num = 0開始

num = 1
[8, 3, 5, 6, 1]
 ^  ^
(8 > 3) 兩個位子交換

num = 2
[3, 8, 5, 6, 1]
    ^  ^
(8 > 5) 兩個位子交換

num = 3
[3, 5, 8, 6, 1]
       ^  ^
(8 > 6) 兩個位子交換

num = 4
[3, 5, 6, 8, 1]
          ^  ^
(8 > 1) 兩個位子交換

[3, 5, 6, 1, 8]

排序完一次，num 變成了 4，可以發現，陣列內有幾個元素，就要比較 (n-1) 次，而要把所有元素排序完，又需要 n 次。 所以一個完整的泡沫排序所需的時間是 n(n-1) => n2，即 O(n2)。

Bubble Sort 的時間複雜度是多少？ O(n2)

泡沫排序實作

現在來練習一下泡沫排序吧！

data = [3, 5, 6, 1, 8]
def bubble_sort_1(l):
    data_len = len(l)
    for run_time in range(data_len):
        for index in range(1, data_len):
            this_data = l[index]
            prev_data = l[index - 1]
            if prev_data > this_data:
                l[index] = prev_data
                l[index - 1] = this_data
        
    
bubble_sort_1(data)
print ("Pass" if (data[0] == 1) else "Fail")

練習程式碼

Resource

• 泡沫排序
• 【舌尖上的演算法】Day7 – Brute Force - Bubble Sort

• ← Previous Post
• Next Post →