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では残念ながらバケットソートでも組み込みソートより時間がかかりました。

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