Internet Explorerよりも速くソートできたよ：コーディングに役立つ！ アルゴリズムの基本（5）（4/4 ページ）

[山下寛人，オイシックス株式会社]

バケットソート―比較せずに振り分ける

　まだあきらめてはいけません。ほかにもソートのアルゴリズムはあります。

　いままでのソートは、値を比較してソートしていました。これとは異なるアプローチでのソート手法があります。それがバケットソートです。

　ソートの値の範囲をいくつかの範囲に分割します。例えば、値の範囲が1〜100だとしたら、1〜10、11〜20、21〜30といった具合に10ずつの範囲に分けます。分けた範囲ごとに入れ物を作ります。この入れ物がバケットです。

　配列から値を1個ずつ取り出してバケットに入れていきます。バケットに複数の値が入る場合もありますので、それぞれのバケットの中はリストにしておきます。バケットに値を入れようとしたとき、すでに入っているものがあったら挿入ソートの要領でリストに値を追加します。

　すべての値をバケットに格納したら、順に値をバケットから取り出していきます。これでソートされた状態になっているはずです。

イラストで見るバケットソート

　では例を挙げて説明します。

　1〜10の範囲の数をソートします。バケットの値の範囲を1ずつとします。こうすると配列のインデックス＝値とできて簡単に実装できます。

　元の配列から最初の値の2を取り出します。これをバケットの2番に入れます。

　順に元の配列を見ていきバケットに入れていきます。2つ目の「2」が出てきたときは、2のバケットに追加します。ここではバケットに入る値はすべて同じなので単純に追加すればよいですが、バケットを値の範囲で取っている場合は違う値になる場合があります。その場合は挿入ソートで値をバケットの中のリストに挿入します。

　以後同様にバケットに値を追加していきます。

　あとはインデックス1のバケットから順に値を取り出していけばソートの出来上がりです。

　バケットソートは分かりやすく高速です。ただし、あらかじめソートされる値の範囲が分かっている必要があります。

　また、一般的な配列の実装では、バケットの分だけ先にメモリ領域が確保されます。例えば、ほとんどの値が10以下で、１つだけ1000000という値があったとしたら、100万個分の配列のメモリ領域が取られることになり、非常に無駄が大きくなります。

バケットソートの実装

　それではバケットソートを実装しましょう。前のコードの46行目、「末尾8」とあるところの次の行以降に以下のコードを追加してください。

<hr/>
バケットソート<br/>
<span id="bucket"></span>
<script type="text/javascript">
Array.prototype.bucketSort = function() {
  var bucket_array = new Array(this.length);
  for (var i = 0; i < this.length; i++) {
    if (bucket_array[this[i]] === undefined) {
      bucket_array[this[i]] = [];
    }
    bucket_array[this[i]].push(this[i]);
  }
 
  var k = 0;
  for (var i = 0; i < bucket_array.length; i++) { 
    if(bucket_array[i] === undefined) { continue; }
    for(var j = 0; j < bucket_array[i].length; j++) {
      this[k] = bucket_array[i][j];
      k++;
    }
  }
  this.display();
} 
var bucket = arrayForDisplay.clone();
bucket.view_id = "bucket";
bucket.display();
bucket.bucketSort(compare);
var bucketForTime = arrayForTime.clone();
func = function() { bucketForTime.bucketSort(compare); }
time(func, "バケットソート", "bucket");
</script>

　プログラムを解説します。

7〜12行目

バケットに順に値を格納していきます。

14〜21行目

順にバケットから値を取り出していきます。

　それでは実行してみましょう。なんと！ 組み込みのソートよりも高速になりました。苦労のかいもあり、ついに組み込みソートに勝利することができました。

　なぜ、より高速になったのでしょうか。バケットソートが高速ということもありますが、今回の実装は値が整数で順序も固定ということも理由として考えられます。

　組み込みソートでは整数でない小数や文字列のソートや順序付けもcompare関数で自由にカスタマイズできます。また、IEの実装が遅いことも挙げられます。Firefoxでは残念ながらバケットソートでも組み込みソートより時間がかかりました。

　さて、たくさんのソートアルゴリズムを紹介してきました。代表的なものは一通り紹介しましたが、まだほかにもありますので興味があれば調べてみてもよいでしょう。次回は探索アルゴリズムを紹介します。

著者紹介

山下 寛人

オイシックス株式会社

「次回」へ

「コーディングに役立つ！ アルゴリズムの基本」バックナンバー

• レコメンデーションとエディットグラフ
• データを加工して圧縮率を高めよう
• データ量を操る圧縮／展開を究めよう
• 文字列の中から効率良くキーワードを探し出せ
• Firebugで探索アルゴリズムを見ていこう
• Internet Explorerよりも速くソートできたよ
• Internet Explorerよりも速くソートできるかな
• 再帰でハノイの塔を攻略せよ
• データ構造の選択次第で天国と地獄の差
• いまさらアルゴリズムを学ぶ意味