クイックソート

クイックソート

クイックソートのアニメーション
クラス	ソート
最悪計算時間	$\mathrm {O} (n^{2})$
最良計算時間	$\mathrm {O} (n\log n)$
平均計算時間	$\mathrm {O} (n\log n)$
最悪空間計算量	$\mathrm {O} (n)$

クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。

n個のデータをソートする際の最良計算量および平均計算量はO$(n\log n)$である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO$(n^{2})$である。また数々の変種がある。 安定ソートではない。

アルゴリズム

1. 適当な数（ピボットという）を選択する（この場合はデータの総数の中央値が望ましい）
2. ピボットより小さい数を前方、大きい数を後方に移動させる （分割）
3. 二分割された各々のデータを、それぞれソートする

実際にこれを実現するためのアルゴリズムは色々考えられるが、一例を挙げると以下のようなものがある。

1. ピボットとして一つ選びそれをPとする。
2. 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
3. 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
4. iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。
5. 2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。

注：このアルゴリズムでは、領域の左端の値が領域内で最小かつ同じ値が他の位置に無い場合、ピボットとしてその値を選ぶと同じ領域を再帰的に呼び出す無限ループとなってしまう。

ピボットは、通常、データ列からランダムに選んだり、データ列中の適当な三つ程度の数の中央値を選ぶ。このように、ピボットの選び方を工夫することで、最悪計算時間がかかってしまうような入力データ列の可能性を抑える。

他にも、ピボットを選ぶ前に入力データ列をランダムに並べ替える、などの手法を上記の工夫と合わせて使うことで、入力データ列のソートに最悪計算時間を必要とする可能性を抑えることができる。

また、再帰的にソートする際、対象となるデータの数が少なくなったら、挿入ソートなどの別のアルゴリズムを適用することで高速化する手法が研究されている。

アルゴリズムの動作例

クイックソートの動作を図示したもの。赤くなっているのがピボット

確定した部分は太文字で表す。ピボットには下線を引く。

初期データ: 8 4 3 7 6 5 2 1

• 中央付近に位置する7をピボットとする。左から7以上を探索して8を発見。右から7未満を探索して1を発見。前者が左にあるため入れ替え。

  1 4 3 7 6 5 2 8

• 次の位置から探索を継続。7と2を発見して入れ替え。

  1 4 3 2 6 5 7 8

• 次の位置から探索を継続。7と5を発見。前者が右にあるため探索終了。左からの探索で最後に発見した位置（7の位置）の左で分割。

  1 4 3 2 6 5 | 7 8

• 「1 4 3 2 6 5」の領域で2をピボットとして探索。左からの探索で4、右からの探索で2を発見、前者が左にあるため入れ替え。

  1 2 3 4 6 5 | 7 8

• 次の位置から探索を継続。3と2を発見。前者が右にあるため探索終了。3の左で分割。

  1 2 | 3 4 6 5 | 7 8

• 「1 2」の領域を2をピボットとして探索、双方とも2を発見、同じ位置であるため探索終了。2の左で分割。「1」「2」の領域は確定。

  1 | 2 | 3 4 6 5 | 7 8

• 「3 4 6 5」の領域を6をピボットとして探索。6と5を発見、前者が左にあるため入れ替え。

  1 | 2 | 3 4 5 6 | 7 8

• 次の位置から探索を継続。6と5を発見するが前者が右にあるため探索終了。6の左で分割。「6」は確定。

  1 | 2 | 3 4 5 | 6 | 7 8

• 「3 4 5」の領域を4をピボットとして探索。双方4を発見して終了するため4の左で分割。「3」は確定。

  1 | 2 | 3 | 4 5 | 6 | 7 8

• 「4 5」の領域を5をピボットとして探索。双方5を発見して終了するため5の左で分割。「4」「5」は確定。

  1 | 2 | 3 | 4 | 5 | 6 | 7 8

• 「7 8」の領域を8をピボットとして探索。双方8を発見して終了するため8の左で分割。すべて確定。

  1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

実装例

C言語によるクイックソートの実装例を示す。

typedef int value_type; /* ソートするキーの型 */

/* x, y, z の中間値を返す */
value_type med3(value_type x, value_type y, value_type z) {
    if (x < y) {
        if (y < z) return y; else if (z < x) return x; else return z;
    } else {
        if (z < y) return y; else if (x < z) return x; else return z;
    }
}

/* クイックソート
 * a     : ソートする配列
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 */
void quicksort(value_type a[], int left, int right) {
    if (left < right) {
        int i = left, j = right;
        value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2 ではオーバーフローしてしまう */
        while (1) { /* a[] を pivot 以上と以下の集まりに分割する */
            while (a[i] < pivot) i++; /* a[i] >= pivot となる位置を検索 */
            while (pivot < a[j]) j--; /* a[j] <= pivot となる位置を検索 */
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp; /* a[i], a[j] を交換 */
            i++; j--;
        }
        quicksort(a, left, i - 1);  /* 分割した左を再帰的にソート */
        quicksort(a, j + 1, right); /* 分割した右を再帰的にソート */
    }
}

次にSchemeによるクイックソートの実装例を示す。

(require-extension srfi-1)              ; SRFI 1 の呼び出し方は実装依存(場合によってはデフォルト)。これは Chicken Scheme の例。

(define (qsort f ls)
  (if (null? ls)
      '()
      (let ((x (car ls)) (xs (cdr ls)))
        (let ((before
               (qsort f (filter (lambda (y) ; filter は SRFI 1 の手続き
                                  ;; compose は Chicken、Gauche、Guile、Racket 等に備わってる「合成関数を作る」手続き。
                                  ;; 詳細は Paul Graham の On Lisp
                                  ;; http://www.asahi-net.or.jp/~kc7k-nd/onlispjhtml/returningFunctions.html
                                  ;; を参照。
                                  ((compose not f) x y)) xs)))
              (after
               (qsort f (filter (lambda (y) ; filter は SRFI 1 の手続き
                                  (f x y)) xs))))
          (append before (cons x after))))))

次にPythonによるクイックソートの実装例を示す。

import statistics

def qsort(f, lst):
    if lst == []:
        return []
    else:
        pivot = int(statistics.median(lst))
        xs = [i for i in lst if i != pivot]
        before = qsort(f, [i for i in xs if not f(pivot, i)])
        after = qsort(f, [i for i in xs if f(pivot, i)])
        return before + [pivot] + after

関連項目

• ランダウの記号
• イントロソート

外部リンク

• クイックソート:アルゴリズム - PythonとC言語のコードで紹介．