iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 1
0

拉蒙碎碎念

還記得以前剛學程式設計的時候,老師都會從幾個較簡單的演算法教起,讓學生比較好學也快上手。其實演算法就是在學邏輯,語法啊、技巧啊,我個人倒覺得是其次。因此之後的文章都會著重在邏輯的概念,語法和效率上或許可以更好,但我偏不改,至少簡單明瞭。(笑)

桶子排序法 (Bucket Sort) 想法很簡單,其實就是準備幾個桶子,將要排序的資料分類丟至指定的桶子中,再依序將桶子裡的東西取出。有點類似資源回收的概念啦~

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

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

並由小到大排序成:

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

1. 準備桶子

首先要來準備桶子,因為成績最高為 100 分,很簡單的做法就是準備 101 個桶子(因有有人可能 0 分)。

max_score = 100
bucket = []
for i in range(max_score+1):
    bucket.append(0)

還沒丟東西,所以桶子裡面都是空的,值都為 0。

2. 丟垃圾 分類成績

將成績一一讀取,並丟到相對應的桶子,有幾個就加幾個。

for score in data:
    bucket[score] = bucket[score] + 1

3. 回收垃圾 讀取成績

先設一個游標,第二行是依序讀取桶子裡的資料,當桶子的資料不為 0 的時候,表示我們有在裡面存放成績。最後三行代表每個桶子都有編號,我們將編號存回 data 裡面,看有幾個就存幾個。

index = 0
for i in range(len(bucket)):
    if bucket[i] != 0:
        for j in range(bucket[i]):
            data[index] = i
            index += 1

就這樣,默默的把垃圾成績分類再撿出來還依序排好,覺得真的是櫻櫻美代子哈哈。

其實Python就有內建的函式sort()resorted()可以做陣列的排序。
但問題是當資料量大的時候,內建的函式不一定會比較快,所以數學家才會發明一堆演算法,就是為了要讓工作更快、更快、再更快。

除了讓事情更有效率,也學到了邏輯呢!

全部的程式碼

程式時間複雜度:O(M+N)

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

def bucketsort(data):
    max_score = 100
    bucket = []
    
    for i in range(max_score+1):
        bucket.append(0)
    for score in data:
        bucket[score] = bucket[score] + 1

    index = 0
    for i in range(len(bucket)):
        if bucket[i] != 0:
            for j in range(bucket[i]):
                data[index] = i
                index += 1

bucketsort(data)
print(data)

花式自虐 進階練習

再如果假設我們的資料還包含了姓名在內,那要如何排序呢?

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

其實原理都差不多,只是我將桶子數量變少,並且將桶子裡的姓名也依照字母排序,其中用的就是內建的函式resorted()

完整程式碼:

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

def bucketsort_hash(data):
    max_score = 100
    bucket = []
    bucket_num = lambda x: int(x/33)
    
    for i in range(bucket_num(max_score)+1):
        bucket.append([])

    for x in data:
        index = bucket_num(x[1])
        bucket[index].append(x)

    for i, flag in enumerate(bucket):
        if flag != [] :
            bucket[i] = sorted(bucket[i], key=lambda x: x[1])

    index = 0
    for i in bucket:
        if i != []:
            for j in i:
                data[index] = j
                index += 1

bucketsort_hash(data)
print(data)

以上的範例是用陣列來結合名字和成績,但其實也可以用字典來做運算,就留待讀者去思考了。


下一篇
[演算法] 泡沫排序 (Bubble Sort)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言