ビンソート （Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、比較によらない整列であるビンソート（Bin Sort）について学んでいきます。

ビンソートとは

前回までで学んだ整列は、いずれも要素同士を比較して行っていました。

今回学ぶビンソート（Bin Sort）は、これらの比較を行わないで整列させるアルゴリズムとなります。

原理としては単純で、入力するデータの値の範囲だけ配列を用意し、入力する値をインデックスとして、ビンの中に格納していきます。

最終的にビンの先頭から値を取り出すことで、データが昇順に整列されています。

なお、binとは「蓋付きの大きな容器」を意味します。

ビンソートはの計算量で整列ができる反面、以下の欠点があります。

1. 値の重複は認められない
2. 値はある範囲に収まる整数でなければならない

上記の1は、連結リストにより拡張させることもできますが、仕組みとして大掛かりになります。

またある範囲分の配列を確保しなければならない為、場合によっては無駄なメモリ領域を使うと同時に計算量も増加していきます。

例えば1～10,000までの範囲の値を10個整列させる場合、の単純な整列アルゴリズムのほうが速くなってしまいます。

Pythonでビンソートを実装してみる

それでは、Pythonでビンソートを実装してみます。

# bin_sort.py
size = 10

def bin_sort(lst):
    bin = [None for _ in range(size)]
    for i in range(len(lst)):
        bin[lst[i]] = lst[i]
    j = 0
    for i in range(size):
        if bin[i]:
            lst[j] = bin[i]
            j += 1
lst = [3,5,8,1,4,2,9]
print(lst)
bin_sort(lst)
print(lst)

動作確認

それでは上記で作成したスクリプトを実行してみます。

 > python bin_sort.py
 [3, 5, 8, 1, 4, 2, 9]
 [1, 2, 3, 4, 5, 8, 9]

ビンの空の部分にはデータが入っていないことを示すフラグ（None）を入れておき、データが入っていることが確認できれば、元の配列に順番に格納していきます。

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)