『Pythonで体験してわかるアルゴリズムとデータ構造』メモその4/バケットソートの制約を知ろう
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第4章にちょろっと書いてあったバケットソートについて書いていく。
バケットソートについて
バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。
バケットソート - Wikipedia
ここでいうバケットとはバケツのこと。ビンソートともいう
事前に用意したバケツに数字を置いていくというのが特徴。
用意したバケツの番号へ同じ番号のデータを順番に渡してあげるため、最良計算量はO(n)。
数字同士の比較が存在しないため、その分処理が速いため早いソートになるが、制約が多め。
事前にバケツを用意する、つまり最初に渡される数字分の要素を用意してあげる必要性があるため、その時点でまずメモリを使用する。
そのため要素数が多すぎるとメモリを使い切ってしまう可能性がある。
また、特徴上渡す値は整数である必要があり、数字の重複が許されない。
数字の重複を許すバケットソートが分布数え上げソート。
バケットソートのイメージは以下
実装
分布数え上げソートで実装。
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]