検索
連載

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

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

[山下寛人，オイシックス株式会社] PC用表示 関連情報
Share
Tweet
LINE
Hatena
前のページへ | 　　　　　　

シェルソート―グループごとに挿入ソート

　次はシェルソートです。ここから徐々に複雑になってきます。

　シェルソートは挿入ソートの改良版です。挿入ソートではあまりよいパフォーマンスが出ませんでしたが、実はソート済みの状態に近い集合をソートする場合は高速です。ソート済み配列の後ろから挿入していくときに比較する回数が少なくて済むからです。この特徴を生かして高速化を図ります。

　元の集合を、何個か置きに要素を取り出して1つのグループにします。このグループで挿入ソートを行います。1つずらして同じようにグループを作り、挿入ソートを行います。こうして全体をいくつかのグループに分けてそれぞれ挿入ソートを行います。すると、完全にソートはされていないですがソート済みの状態に近づきます。

　この状態で全体を挿入ソートすると高速にソートすることができます。要素の数が多い場合、いったん大きい間隔でグループを作り、全体を処理したら徐々に間隔を狭めてグループを作り、挿入ソートを繰り返していきます。

図3　シェルソート
図3　シェルソート

　それではプログラムを紹介します。前のプログラム26行目、「末尾4」のコメントの後にプログラムを追加してください。

<hr/>
シェルソート<br/>
<span id="shell"></span>
<script type="text/javascript">
Array.prototype.shellSort = function(compare) {
  var h = new Array();
  for(var i = 1; i <= this.length / 2; i += (3*i) + 1) {
    h.push(i);
    }
 
  for (var i = h.length-1; 0 <= i; i--) {
    for (var j = 0; j < h[i]; j++) {
      this.insertionSort(compare, j, h[i]);
    }
  }
}
var shell = arrayForDisplay.clone();
shell.view_id = "shell";
shell.display();
shell.shellSort(compare);
var shellForTime = arrayForTime.clone();
func = function() { shellForTime.shellSort(compare); }
time(func, "シェルソート", "shell");
</script><!-- 末尾5 -->

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

　配列hは、何個飛ばしでグループ化するかを格納する配列です。最初は間隔を大きく取って細かくグループ分けし、徐々に間隔を狭めていきます。挿入ソートのところでoffset、stepといったものを用意したのはここで使用するためです。

　それでは実行してみましょう。処理時間がぐっと縮んだと思います。まだ組み込みのソートより遅いですが、約2倍といったところまで近づきました。もしかしたら勝てるかもしれない気がしてきました。

クイックソート―名は体を表す？

　続いてクイックソートです。

　以後の説明では、配列のインデックスが小さい方を左側、大きい方を右側として説明します。

　クイックソートは集合の中からある値を取り出し、それより小さい値を左側に、大きい値を右側に集めます。左側は左側の中で同じようにある値を取り出し小さい値と大きい値に分けます。さらに分けた中で同じように小さい値と大きい値に分けていきます。これを繰り返していきます。これ以上分けられなくなったらその部分はソート完了です。

　次に右側のグループで同じように値を分けていきます。全部終わると全体がソートされた状態になります。ちなみに名前の由来は非常に高速であることです。これは期待が持てそうです。

図4　クイックソート
図4　クイックソート

　それではプログラムを紹介します。これまで同様、前の24行目の「末尾5」のコメントの後に次のプログラムを追加してください。

<hr/>
クイックソート<br/>
<span id="quick"></span>
<script type="text/javascript">
Array.prototype.quickSort = function(compare, left, right) {
  left = (left === undefined) ? 0 : left;
  right = (right === undefined) ? (this.length-1) : right;
  if(right <= left) { return; }
 
  var partition = left;
  for (var i = left+1; i <= right; i++) {
    if (compare(this[i], this[left]) < 0) {
      partition++;
      this.swap(partition, i);
    }
  }
  this.swap(left, partition);
  this.display();
 
  this.quickSort(compare, left, partition-1);
  this.quickSort(compare, partition+1, right);
}
var quick = arrayForDisplay.clone();
quick.view_id = "quick";
quick.display();
quick.quickSort(compare);
var quickForTime = arrayForTime.clone();
func = function() { quickForTime.quickSort(compare); }
time(func, "クイックソート", "quick");
</script><!-- 末尾6 -->

　このプログラムは再帰を使っています（20、21行目）。再帰については第3回「再帰でハノイの塔を攻略せよ」で詳しく解説していますのでごらんください。

　quickSort関数の引数にはleftとrightがあります。これは配列の中のどこからどこまでをクイックソートの対象にするかを指定するものです。分割しながらクイックソートを繰り返すので範囲が指定できるようにしてあります。

　10行目の変数partitionは右と左をどこで分けるかを示す変数です。最初は一番左のleftに設定しておきます。

　このプログラムでは、大小の基準になる数値は、一番左の値を使うようにしています。そのため11行目のループはleft+1から右に進むようループしています。

　12行目、それぞれの要素と基準の値(this[left])を比較し、小さければpartitionを1つ右に進め、partitionの位置と交換します。こうして小さい値が左側に集められ、partitionは右と左の間を指すようになります。

　ループが終わると一番真ん中の値が一番左にある状態になります。そのためleftとpartitionの要素を交換します（17行目）。

　小さい値と大きい値に分かれたらそれぞれの中でクイックソートを行います（20、21行目）。

　それでは実行してみましょう。いかがだったでしょう。なかなか高速でシェルソートと同じくらいの実行時間になります。しかし組み込みのソートにはまだ及びませんでした。

クイックソートのパフォーマンス

　クイックソートは高速ですが場合によっては遅くなる可能性があります。次のような配列を考えてみましょう。

図5　クイックソートが苦手な配列
図5　クイックソートが苦手な配列

　一番左の値を基準とした場合、右側の要素はすべて10より小さくなります。従って配列が分割されません。次のループでも9を基準値としましたが右側の要素はすべて9より小さい値です。また配列が分割されない結果になります。

　この動作は選択ソートやバブルソートに似ています。最悪の場合一番大きい値が次々に右に移り、分割が行われない可能性があります。この場合の計算量は選択ソートやバブルソートと同等になってしまいます。

　こうなってしまうのは基準値の選び方がよくないからです。基準値は要素の値のちょうど真ん中になる場合が最もパフォーマンスがよくなります。

　そこで基準値の選び方によってパフォーマンスをさらに改善することが考えられます。今回は一番左の値を基準にしましたが、ランダムに選ぶ方法や、要素を3つだけ取り出してその真ん中の値を基準にする方法などがあります。

　ただし最悪のケースになる確率は非常に低いです。1回基準値の選択に失敗したとしても続けて失敗する可能性が低いので、全体として平均的によいパフォーマンスが期待できます。

　今回は残念ながら組み込みのソートより高速にソートすることはできませんでした。しかし、まだまだソートのアルゴリズムはたくさんあります。次回は勝つことができるのでしょうか。

著者紹介

山下 寛人

オイシックス株式会社


「次回」へ


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

Copyright © ITmedia, Inc. All Rights Reserved.

前のページへ | 　　　　　　
ページトップに戻る