すのふら

すのふら

日々の備忘録

『Pythonで体験してわかるアルゴリズムとデータ構造』メモその4/バケットソートの制約を知ろう

Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。

Pythonで体験してわかるアルゴリズムとデータ構造

Pythonで体験してわかるアルゴリズムとデータ構造

第4章にちょろっと書いてあったバケットソートについて書いていく。



バケットソートについて

バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。
バケットソート - Wikipedia

ここでいうバケットとはバケツのこと。ビンソートともいう

事前に用意したバケツに数字を置いていくというのが特徴。

用意したバケツの番号へ同じ番号のデータを順番に渡してあげるため、最良計算量はO(n)。
数字同士の比較が存在しないため、その分処理が速いため早いソートになるが、制約が多め。

事前にバケツを用意する、つまり最初に渡される数字分の要素を用意してあげる必要性があるため、その時点でまずメモリを使用する。
そのため要素数が多すぎるとメモリを使い切ってしまう可能性がある。

また、特徴上渡す値は整数である必要があり、数字の重複が許されない。

数字の重複を許すバケットソートが分布数え上げソート。

バケットソートのイメージは以下

f:id:snofra:20190921020917p:plain



実装

分布数え上げソートで実装。

def bucket_sort(lst):
    bucket = [None for _ in range(max(lst)+1)]
    print(bucket)
    # バケットにデータを格納していく
    # input側で重複した値を存在した時は加算する
    for i in lst:
        if bucket[i] == None:
            bucket[i] = i
        else:
            bucket[i] += i
    
    print(bucket)
    # 書き戻し作業
    j = 0
    for bucket_num, lst_num in enumerate(bucket):
        if lst_num == None:
            continue
        if lst_num == 0:
            lst[j] = lst_num
            j += 1
            continue
        
        print("要素番号, データ", bucket_num, lst_num)
        
        for k in range(lst_num // bucket_num):
            # 要素番号よりも格納データのデータが大きい場合、重複したデータのためバケットの番号をセット
            if lst_num > bucket_num:
                lst_num = bucket_num
            lst[j] = lst_num
            print(lst)
            j += 1
            
lst = [1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
print("処理前", lst)
print()
bucket_sort(lst)
print()
print("処理後", lst)
処理前 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0]

[None, None, None, None, None, None, None, None]
[0, 2, 4, 6, 4, 5, None, 7]
要素番号, データ 1 2
[0, 1, 3, 4, 5, 3, 2, 1, 7, 0]
[0, 1, 1, 4, 5, 3, 2, 1, 7, 0]
要素番号, データ 2 4
[0, 1, 1, 2, 5, 3, 2, 1, 7, 0]
[0, 1, 1, 2, 2, 3, 2, 1, 7, 0]
要素番号, データ 3 6
[0, 1, 1, 2, 2, 3, 2, 1, 7, 0]
[0, 1, 1, 2, 2, 3, 3, 1, 7, 0]
要素番号, データ 4 4
[0, 1, 1, 2, 2, 3, 3, 4, 7, 0]
要素番号, データ 5 5
[0, 1, 1, 2, 2, 3, 3, 4, 5, 0]
要素番号, データ 7 7
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]

処理後 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7]

参照

バケットソート

バケットソート/ビンソート : アルゴリズム

分布数え上げソート : アルゴリズム

www.youtube.com