初心者がpython３でソートアルゴリズムを実装してみる【バケットソート＆基数ソート】
バケットソート
バケットソートは、ソートのアルゴリズムの一つ。バケツソート、ビンソート（backetとbinでそのままですね）などともいわれる。
データ数ｎに対して、バケツ数ｎを用意すると、O（n）でソートが完了するはずの最強ソートに一瞬見えてしまうソートアルゴリズムです。
ただし、データの値の範囲のバケツを必ず用意しなければならないので、実用的ではない場面の多いアルゴリズムです。
似た仕組みのものに、度数分布を記録していきソートを行う数え上げソートや、桁ごとにバケットソートを行う基数ソートがあります。
アルゴリズム
データに重複がない場合、アルゴリズムはとても単純です。
データ：[ 3, 1, 5, 4, 2 ]
| バケツ | B[1] | B[2] | B[3] | B[4] | B[5] |
| データ |
①左から順番にデータを取り出します
データ：[1, 5, 4, 2 ] → 3
| バケツ | B[1] | B[2] | B[3] | B[4] | B[5] |
| データ |
②バケツの3番に3を格納
データ：[1, 5, 4, 2 ]
| バケツ | B[1] | B[2] | B[3] | B[4] | B[5] |
| データ | ３ |
③１をとりだしバケツに
データ：[5, 4, 2 ]
| バケツ | B[1] | B[2] | B[3] | B[4] | B[5] |
| データ | １ | ３ |
④以下繰り返しで、
データ：[2 ]
| バケツ | B[1] | B[2] | B[3] | B[4] | B[5] |
| データ | １ | ３ | ４ | ５ |
④２を取り出しバケツに入れ、ソート完了
データ：[ ]
| バケツ | B[1] | B[2] | B[3] | B[4] | B[5] |
| データ | １ | ２ | ３ | ４ | ５ |
データの入れ替えや、比較なしにソートが完了してしまう、謎アルゴリズムです。
実装・結果
実装は、特に何の工夫もなく初心者丸出しでやってみました。
もっと効率の良い書き方はあると思います。
[3, 9, 5, 1, 2, 4, 8, 6, 7, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
並べ替えられてますね（笑）
基数ソート（Radix sort）
バケットソートを、桁ごとに行う方法です。バケットソートでは、値の最大値から、最小値の範囲でバケツを用意しなければなりませんでした。
基数ソートでは、基数の桁ベースでソートを行うので、１０進数ならバケツは１０こ、２進数なら、２ビット区切りなら４つ、３ビット区切りなら８つのバケツでソート可能です。
アルゴリズム
下の桁から上の桁に向けて、桁ごとにバケットソートを行います。
１の位でソート
データ：[56, 89, 12, 45, 78, 105, 23, 26, 33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ |
①まず、１の位でバケットソートを行います。
データ：[89, 12, 45, 78, 105, 23, 26, 33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 56 |
データ：[12, 45, 78, 105, 23, 26, 33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 56 | 89 |
データ：[45, 78, 105, 23, 26, 33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 56 | 89 |
データ：[78, 105, 23, 26, 33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 45 | 56 | 89 |
データ：[105, 23, 26, 33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 45 | 56 | 78 | 89 |
データ：[23, 26, 33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 45, 105 | 56 | 78 | 89 |
データ：[26, 33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 23 | 45, 105 | 56 | 78 | 89 |
データ：[33, 63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 23 | 45, 105 | 56,26 | 78 | 89 |
データ：[63]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 23, 33 | 45, 105 | 56,26 | 78 | 89 |
データ：[]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 23, 33, 63 | 45, 105 | 56,26 | 78 | 89 |
②データを、順番に取り出します。
データ：[12, 23, 33, 63, 45, 105, 56, 26, 78, 89]
③１０の位でソート
データ：[12, 23, 33, 63, 45, 105, 56, 26, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ |
データ：[23, 33, 63, 45, 105, 56, 26, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 |
データ：[33, 63, 45, 105, 56, 26, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 23 |
データ：[63, 45, 105, 56, 26, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 23 | 33 |
データ：[45, 105, 56, 26, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 23 | 33 | 63 |
データ：[105, 56, 26, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 23 | 33 | 45 | 63 |
データ：[56, 26, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 105 | 12 | 23 | 33 | 45 | 63 |
データ：[26, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 105 | 12 | 23 | 33 | 45 | 56 | 63 |
データ：[78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 105 | 12 | 23, 26 | 33 | 45 | 56 | 63 |
データ：[89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 105 | 12 | 23, 26 | 33 | 45 | 56 | 63 | 78 |
データ：[]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 105 | 12 | 23, 26 | 33 | 45 | 56 | 63 | 78 | 89 |
④データを、順番に取り出します。
データ：[105, 12, 23, 26, 33, 45, 56, 63, 78, 89]
⑤１００の位でソート
データ：[105, 12, 23, 26, 33, 45, 56, 63, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ |
データ：[12, 23, 26, 33, 45, 56, 63, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 105 |
データ：[23, 26, 33, 45, 56, 63, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12 | 105 |
データ：[26, 33, 45, 56, 63, 78, 89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12,23 | 105 |
（省略）
データ：[89]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12,23, 26, 33, 45, 56, 63, 78 | 105 |
データ：[]
| バケツ | B[0] | B[1] | B[2] | B[3] | B[4] | B[5] | B[6] | B[7] | B[8] | B[9] |
| データ | 12,23, 26, 33, 45, 56, 63, 78, 89 | 105 |
⑥データを、順番に取り出します。
データ：[12, 23, 26, 33, 45, 56, 63, 78, 89, 105]
ソート完了！
実装・結果
なんか、うまく表現できなかった気がします（笑）
一応ちゃんと動いてはいるようです。
[249, 100, 466, 596, 715, 360, 630, 627, 797, 762]
[100, 249, 360, 466, 596, 627, 630, 715, 762, 797]
所感
バケットソートと、基数ソートを実装してみました。メモリさえあれば早く動くソートですが、余り実用されているところは見ない気がします。
可視化もやろうかなと思ったのですが、数値をバケツに移動するところをどう表現しようか悩んでちょい保留しました。Javaかjavascriptなら簡単なのになぁと思ったりもしたけど、ちょいと考えてみます。
