文系が学ぶコンピューターサイエンス：第２回【計算量、クイックソート】

今回学ぶこと

ソートアルゴリズムの中でも名前通り高速と言われるクイックソート。
加えて、前回触れなかった計算量の概念について。

「クイックソート」とは？

早いソート。後述ですが最初何やってるのかわかりませんでした。
アルゴリズムが可視化されている動画見てもさっぱりわかりません。

f:id:u_tis:20150121234821p:plain
ゲーマーなのでクイックマンを思い出さずにはいられない。

クイックソートは、以下のような手順でソートします。

ソートを分割するために基準値を決める
左から順に、基準値より大きな値を探す
右から順に、基準値より小さな値を探す
交換する
基準値の左は小さい値、右は大きい値になったら、終了
これが完全に終了するまで再帰

です。基準値より大小の値を探すときは、配列で1個ずつ基準値に近づいていって、もし調べる対象がすれ違ったら（基準値の周りが全部大小関係が整理されたら）、そのサイクルは終了です。
今回のコードでは、基準値を左端の値で置いてます。
これは真ん中を基準値にとったりするケースもありますが、
乱数の配列ならどっちが明確に早いとかはとくにないっぽいです。

※参考
Algorithms with Python / 整列 (ソート)
クイックソート
 Computer science in JavaScript: Quicksort | NCZOnline

「時間計算量」とは？

バブルソートのところで触れ忘れたんですが、アルゴリズムを勉強するときは必ず時間計算量ってやつを知っておいたおいたほうがいいっぽいですね。

時間計算量というのは、「コードへのデータ入力量が多くなった時、どれくらい、どのように処理時間が増加するかを表した式」です。
時間計算量はオーダー記法というやつで書き表されます。
その値は、だいたいループの回数に依存します。
例えば前回やったバブルソートは、最悪の場合すなわち一番時間がかかる場合は全部逆順に並んでいる時ですね。

1 2 3 4 5 6
が正解なら、
6 5 4 3 2 1
のときが最悪。
一個一個前に持ってこなきゃいけない。

このとき、1を左端に持ってくるまでに５回（6-1、抽象化するとn-1回）かかります。
この流れを繰り返すと、2を1の次に持ってくるまで5-1=4回(抽象化するとn-2回)ですし、
これらを合計すると、(n-1)+(n-2)+...+1 = Σn = n(n-1)/2回です。
（これはただの数列の話なのでなんとか文系の僕でもわかります）
で、時間計算量は係数省いて、1とか2とかの誤差の範囲は削って収束させちゃうので、
この場合だと1/2を1にして、n(n-1)のn-1をnにまとめちゃって、結果n^2になります。
ここでオーダー記法ってやつを使って、O(n^2)と表すのが、時間計算量の掟らしいです。

以上、計算量の性質をまとめると、

計算量は、アルゴリズムを評価する為に使用する
計算量は、大体の場合はループの回数と一致する
計算量は、最大指数項のみを残し係数は省く

です。

※参考
アルゴリズム勉強会計算量 - KUT-PG 高知工科大学プログラミング集団 Wiki*

クイックソートはなぜ早い？

クイックソートの話に戻ります。
名前はシンプルなんですが、こいつくっそ理解できないです。
なんでかっていうと、クイックな理由がいまいちわからんからです。
まあ再帰的に処理を分割していくからでしょう。
計算量はこちらを参考にしました。
計算式超丁寧です。ありがとうございます。文系の僕でもわかった。
バブルソートのO(n^2)よりO(nlogn)が小さそうなのはなんとなくわかります。

http://www.jaist.ac.jp/~s-hagiwa/qsort.pdf

クイックソートのコード

以下の通りです。前回からのソースの差分はこちら
<a href="https://github.com/timakin/jsalgo/commit/980d1b4be0747de163721755a0428794f1f3ed5a">timakin/jsalgo</a>
quicksort · 980d1b4 · timakin/jsalgo · GitHub

function Sort() {}
Sort.prototype = {
  swap: function(items, lower, upper) {
    var temp = items[lower];
    items[lower] = items[upper];
    items[upper] = temp;
  },
  // クイックソートの基準値を返す関数
  partition: function (data, bottom, top) {
    var pivot = data[bottom];
    // 両端の値を設定。
    var lower = bottom;
    var upper = top;
    while (lower <= upper) {
      while (data[lower] < pivot) {
        lower++;
      }
      while (data[upper] > pivot) {
        upper--;
      }
      if (lower <= upper) {
        this.swap(data, lower, upper);
        lower++;
        upper--;
      }
    }
    return lower;
  },
  quick: function (data, bottom, top) {
    var self = this;
    if (bottom >= top) { return; }
    // 基準値の周りで並び替えが終わったらそのサイクルは終了。
    // ここからがいわゆるpartition（基準点）を作る処理
    // 便宜上左端の値を基準値にしている。
    var index = self.partition(data, bottom, top);
    self.quick(data, bottom, index-1);
    self.quick(data, index, top);
    return data;
  }
}