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

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

バブルソート―泡が浮かび上がるように

　続いてバブルソートを紹介しましょう。

　配列の0番目の要素と1番目の要素を比較して、0番目の方が大きかったら交換します。次に1番目の要素と2番目の要素を比較して、1番目の方が大きかったら交換します。

　これを配列の末尾まで繰り返すと末尾が一番大きい値になります。また最初から同様に交換していくと、末尾から2番目が2番目に大きい値になります。これを最後まで繰り返して出来上がるとソートされた状態になります。

図1　バブルソート

　交換を繰り返して一番大きい値が徐々に上に浮かび上がっていく様子が、水の中を泡（バブル）が浮かび上がるのに似ていることからバブルソートと呼ばれています。すてきなネーミングですね。

　それではソースコードを紹介します。先ほどのソースの27行目、「末尾2」というコメントがあるところの次の行に以下のコードを追加してください。

<hr/>
バブルソート<br/>
<span id="bubble"></span>
<script type="text/javascript">
Array.prototype.bubbleSort = function(compare) {
  for(var i = this.length-1; 1 <= i; i--) {
    for (var j = 0; j <= (i-1); j++) {
      if(compare(this[j+1],this[j]) < 0) {
        this.swap(j, j+1);
      }
    }
  this.display();
  }
}
var bubble = arrayForDisplay.clone();
bubble.view_id = "bubble";
bubble.display();
bubble.bubbleSort(compare);
var bubbleForTime = arrayForTime.clone();
func = function() { bubbleForTime.selectionSort(compare); }
time(func, "バブルソート", "bubble");
</script><!-- 末尾3 -->

　それでは実行してみましょう。いかがでしょうか。

　選択ソートとだいたい同じくらい時間がかかり、こちらも勝負になりません。残念ながら名前がかっこいい割にパフォーマンスはいまいちのようです。

選択ソートとバブルソートのパフォーマンス

　選択ソートとバブルソートはなぜ遅いのでしょうか。その答えは、ループの回数を考えてみると見えてくるかもしれません。

　配列の要素数を10とすると、10回はループが発生します。その1ループごとに9回、8回、7回、……のループがあります。要素が1つ増えた場合には10回のループが増えます。さらに要素の数が増えると11回増えます。

　こうして要素の数に応じて倍々ゲームのようにループ回数が増えてしまいます。そのため要素の数が増えると極端に遅くなるのです。パフォーマンスを上げるにはループの回数を減らすための工夫が必要になりそうです。

挿入ソート―2つの配列を使って

　次は挿入ソートです。

　ソートする前の状態の配列があるとします。配列を新規に作成し、ソート済み配列とします。ソート済み配列は最初は空の状態です。

　ソート前の配列の中から値を1つ取り出し、ソート済み配列に入れます。元の配列からまた値を1つ取り出し、ソート済み配列の値と比較します。大きいか小さいかで後か前に入れます。元の配列からまた値を取り出します。ソート済み配列の後ろから値を比較していき、取り出した値の方が大きくなったところで値を挿入します。これを繰り返すことで全体をソートします。

図2　挿入ソート

　それではソースコードを紹介します。先ほどのソース22行目、「末尾3」のコメントの後の行に以下のコードを追加してください。

<hr/>
挿入ソート<br/>
<span id="insertion"></span>
<script type="text/javascript">
Array.prototype.insertionSort = function(compare, offset, step) {
  offset = (offset === undefined ? 0 : offset);
  step = (step === undefined ? 1 : step);
 
  for (var i = offset+step; i < this.length; i+=step) {
    tmp = this[i];
    for (var j = i-step; offset <= j; j-=step) {
      if (compare(this[j], tmp) < 0) { break; }
      this[j+step] = this[j];
    }
    this[j+step] = tmp;
    this.display();
  }
}
var insertion = arrayForDisplay.clone();
insertion.view_id = "insertion";
insertion.display();
insertion.insertionSort(compare);
var insertionForTime = arrayForTime.clone();
func = function() { insertionForTime.insertionSort(compare); }
time(func, "挿入ソート", "insertion");
</script><!-- 末尾4 -->

　ソースコードの補足をします。

　offsetとstepという変数がありますが、これは後で使います。

　offsetは配列の途中から先だけをソートの対象にするための変数です。デフォルトは0なので、ここでは先頭から全部をソートの対象にしています。stepはいくつか飛ばしながら挿入ソートをするための変数です。ここでは1なので、要素を飛ばさずに順に処理しています。

　元の配列とソート済みの配列は同じものを使っています。先頭の方からソート済みになっていきます。ループは配列の2番目の要素から始まっています（9行目）。最初の1個は1つだけなのでソート済みと見なせるからです。

　それでは実行してみましょう。処理時間は選択ソート、バブルソートに比べて約半分になりました。それでもまだまだ組み込みのソートに遠く及びません。