Bubble Sort

發表於 2020-12-25 Disqus：

文章字數： 1.6k 所需閱讀時間 ≈ 3 分鐘

Bucket Sort 雖然直覺、簡單好懂，但也遺留了一些問題。舉例來說如果資料很大，就會很浪費空間，或者當資料有小數的時候，沒辦法產生相對應的桶子。

Bubble Sort 想法是這樣的，假設要由小排到大，左邊為小右邊為大，以左邊第一個為基準點，不斷的跟右邊的值比大小，比較小的就往左，大的就停住，然後再從這個大的值繼續往右比，直到最後一個位置。現在比完第一輪了，接著再從最左邊的頭開始，往下比下去。

Bubble

由左至右，兩兩記錄依序互相比較
if (前者 > 後者) then Swap (前者, 後者)

Sort

將未排序好的記錄透過 Bubble 的動作，使之成為排序好的記錄
共需做 n-1 回合，且由第 1 筆資料開始做起，∴ 迴圈: for i = 1 to (n-1)
若在某回合處理過程中，沒有任何 Swap 動作發生，則 Sort 完成，後續回合不用執行

假設我們現在有一筆班上的成績想要排序：

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

計算幾個泡泡

n = len(data)

外圈要跑n-1次

最後剩下最小泡泡不用比較所以 -1 次

for i in range(n-1):
    # code

## 內圈跑n-1-i次（兩兩比較次數）

因為每一圈剩下 n-i 個泡泡每圈比較 n-i-1 次

for j in range(n-i-1):
    # code

## 程式碼

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

n = len(data)
# 總共跑n-1次
for i in range(n-1):
    # 內圈跑n-1-i次
    for j in range(n-i-1):
        if data[j] > data[j+1]:
            data[j], data[j+1] = data[j+1], data[j]
print(data)

[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]

時間複雜度

Best Case

O(n) 當輸入資料已經是由小到大排好時

Worst Case

O(\(n^2\)) 當輸入資料已經是由大到小排好時

Average Case

O(\(n^2\))

空間複雜度

O(1)

練習

data = [['Abby', 58], ['Julia', 44], ['Jane', 31], ['Stephen', 76], ['Ryn', 82],['Justin', 99], ['Caroline', 65], ['James', 87], ['Damon', 25], ['Elena', 76]]

data = [['Abby', 58], ['Julia', 44], ['Jane', 31], ['Stephen', 76], ['Ryn', 82],['Justin', 99], ['Caroline', 65], ['James', 87], ['Damon', 25], ['Elena', 76]]
n = len(data)

for i in range(n-1):
    for j in range(n-i-1):
        if data[j][1] > data[j+1][1]:
            data[j], data[j+1] = data[j+1], data[j]
print(data)

[['Damon', 25], ['Jane', 31], ['Julia', 44], ['Abby', 58], ['Caroline', 65], ['Stephen', 76], ['Elena', 76], ['Ryn', 82], ['James', 87], ['Justin', 99]]

Nicholas Blogger