iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 2
2
Software Development

30天學演算法和資料結構系列 第 2

[演算法] 泡沫排序 (Bubble Sort)

拉蒙碎碎念

其實昨天的桶子演算法雖然直覺、簡單好懂,但也遺留了一些問題。舉例來說如果資料很大,就會很浪費空間,或者當資料有小數的時候,沒辦法產生相對應的桶子。因此在昨天的進階練習的程式碼裏,就偷偷用了雜湊函數(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]

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

動手做做看吧~

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


上一篇
[演算法] 桶子排序法 (Bucket Sort)
下一篇
[演算法] 快速排序法 (Quick Sort)
系列文
30天學演算法和資料結構31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
bojsa
iT邦新手 5 級 ‧ 2020-08-28 04:07:27

您應該是大太快了
第一個迴圈應該是 for i in range(n-1)喔
reference:
https://www.geeksforgeeks.org/python-program-for-bubble-sort/

我要留言

立即登入留言