#Pythonで学ぶアルゴリズム< ビンソート / バケットソート >
はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第23弾としてビンソート（バケットソート）を扱う．
ビンソート（バケットソート）
ビンソートはバケットソートとも呼ばれる．以降ビンソートと呼ぶこととする．
ビンソート: 並べ替える要素が限定されているときに用いられるソート方法．
データ内に各要素がいくつあるのかをカウントし，そのカウント数を使って，並べ替える．そのイメージ図を次に示す．
実装
先ほどの説明をもとにPythonでの実装を行った．なお，参考文献では，決まった要素の参照リストが利用されているが，その参照リストも変えられるような実装を試みた．そのソースコードとそのときの出力を以下に示す．
ソースコード
"""
2021/01/27
@Yuya Shimizu
ビンソート
"""
def bin_sort(data, data_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]):
""" 参照リストの要素がデータにいくつあるのかをカウントし，順に並べていく """
sorted_data = [] #結果を格納する配列
for i in data_list: #要素を基準にカウントを行う
count = 0 #カウントするための変数
for j in data: #各データについて調べる
if j == i:
count += 1 #要素が含まれていればカウント
[sorted_data.append(i) for k in range(count)] #順にカウント分だけその要素を結果として配列に格納
return sorted_data
if __name__ == '__main__':
DATA = [9, 4, 5, 2, 8, 3, 7, 8, 3, 2, 6, 5, 7, 9, 2, 9]
data_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sorted_data = bin_sort(DATA, data_list)
print(f"参照リスト: {data_list}\n\n{DATA} → {sorted_data}")
出力
参照リスト: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 4, 5, 2, 8, 3, 7, 8, 3, 2, 6, 5, 7, 9, 2, 9] → [2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 9, 9]
ソースコード内で定義している関数では，第2引数に参照リストを渡せるが，デフォルトでは[0,1,2,3,4,5,6,7,8,9]となるようにしている．そのため，参照リストを変更するときは，関数を扱うときに第2引数にリストの型で指定すればよい．
感想
ついに，並べ替えアルゴリズムを終えた．少し長かったが，今後役立つと願おう．今回のビンソートは参考文献における"理解度check"の問題であり，様々な書き方があるとは思うが，今の私が思いつく良い方法を示した．次回からも参考文献に沿って学習を進める．残るは後1章分．また楽しみである．
参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社