拉蒙碎碎念

其實昨天的桶子演算法雖然直覺、簡單好懂，但也遺留了一些問題。舉例來說如果資料很大，就會很浪費空間，或者當資料有小數的時候，沒辦法產生相對應的桶子。因此在昨天的進階練習的程式碼裏，就偷偷用了雜湊函數(Hash)，來解決這些問題(我就愛偷吃步，怎麼樣？！哈哈)

但今天要討論的不是雜湊，是泡泡演算法。

泡沫排序 (Bubble Sort) 想法是這樣的，假設要由小排到大，左邊為小右邊為大，以左邊第一個為基準點，不斷的跟右邊的值 定高枝 比大小，比較小的就往左，大的就停住，然後再從這個 礙事的 大的值繼續往右比。如果到很不幸馬上就遇到更大的，再從更大的往右比，直到最後一個位置。現在，已經比完第一輪了(才第一輪？！)，接著再從最左邊的頭開始，往下比下去。

我們用比身高來舉例，分為 1 到 10 ：
矮 ------------------------------------> 高
8　6　1　10　5　3　9　2　7　4
6　8　1　10　5　3　9　2　7　4
6　1　8　10　5　3　9　2　7　4

可惡，8 碰到 10 過不去了，那就只好讓 10 繼續比下去。
6　1　8　10　5　3　9　2　7　4
6　1　8　5　10　3　9　2　7　4
6　1　8　5　3　10　9　2　7　4
6　1　8　5　3　9　10　2　7　4
6　1　8　5　3　9　2　10　7　4
6　1　8　5　3　9　2　7　10　4
6　1　8　5　3　9　2　7　4　10

現在 10 撞牆了，已經稱霸沒得比了，所以再從頭的 6 開始往右比。
6　1　8　5　3　9　2　7　4　10
1　6　8　5　3　9　2　7　4　10
1　8　6　5　3　9　2　7　4　10
.
.
黑箱作業
.
.
1　2　3　4　5　6　7　8　9　10

重複以上的做法，最終我們得到了排列整齊的身高。

現在，我們就來看程式碼怎麼做吧。

接下來就以昨天的成績為例：
程式時間複雜度：O(N^2)

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

def bubblesort(data):
    # 定義資料長度
    n = len(data)
    for i in range(n-2):                   # 有 n 個資料長度，但只要執行 n-1 次
        for j in range(n-i-1):             # 從第1個開始比較直到最後一個還沒到最終位置的數字 
            if data[j] > data[j+1]:        # 比大小然後互換
                data[j], data[j+1] = data[j+1], data[j]

bubblesort(data)
print(data)

結果為：

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

當然，也可以用昨天的進階練習中，帶有姓名的資料來做排序。只要原本的程式碼稍微改動一下就行囉！！

動手做做看吧～

但其實聰明人可以看得出來，這種排序的核心就是雙重迴圈(這時候看不出來的也要說看得出來？！)，這種程式的執行效率當資料量大的時候，效率也是會偏低的。同樣的事情要反覆地從頭做，還好是電腦，不然是人的話可能很快就爆炸了吧(笑)。所以很早的時候就有人在研究要改進，但好像也沒辦法變得更好，最後除了好聽的名字之外，似乎也不是那麼實用呢。