クイックソート

クイックソート（）は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
formula_1 個のデータをソートする際の最良計算量および平均計算量は formula_2（ランダウの記号）である。他のソート法と比べて一般的に最も高速だと言われているが、対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はformula_3である。安定ソートではない。
アルゴリズム.
クイックソートは以下の手順で行われる。
配列の分割方法の一例として、以下のようなものが考えられる：
分割後の要素数が一定の閾値を下回ったら挿入ソートのような「少数の要素に対してより効率的なソート」に切り替える、という手法がある。また、配列の分割方法自体にも様々な変種がある（同時に2つのピボットを選択して3分割する Dual-pivot Quicksort など）。
アルゴリズムの動作例.
確定した部分は太文字で表す。ピボットには下線を引く。
初期データ: 8 4 3 7 6 5 2 1
最悪計算量の回避.
時間計算量.
クイックソートの効率は配列の分割の効率に左右される。再帰の各段階で常に均等に分割される場合が最良であり、時間計算量は formula_2 となる。一方で、常に「1要素と残り全部」のように偏って分割された場合が最悪のケースで、時間計算量が formula_5 に悪化する。
最悪ケースを避けるにはピボットの選択に注意を払う必要がある。たとえば、既にソートされた配列に対して先頭や末尾の要素をピボットとすると最悪ケースとなる。なるべく配列の中央値をピボットとして選べるようにすれば、このようなケースを回避できる。
代表的なピボット選択の戦略として、以下のようなものが挙げられる：
また、ピボットを選ぶ前に配列をランダムに並べ替えるなどの手法によっても、ソートに最悪計算時間を要する可能性を抑えられる。
ただし、いずれの場合も最悪ケースの可能性を完全に排除できるものではない。これに対する根本的な改良として、一定の閾値よりも再帰が深くなったらヒープソートのような formula_2 時間が保証されるアルゴリズムに切り替える方法がある（イントロソート）。
空間計算量.
分割の操作自体は追加の領域を必要としないが、再帰によるコールスタックの消費が空間計算量となる。スタックの消費は平均的には formula_7 となるが、最悪ケースでは formula_8 に増大するため、大きなサイズの配列の場合スタックオーバーフローを起こす危険性がある。
対策として、「分割された配列のうち、要素数が少ない方を常に先に処理する」ことで、空間計算量を最悪 formula_7 に抑えられる。このようにすると、常に均等に分割される（最良時間の）場合に formula_10 スタックとなる一方で、1要素ずつしか分割されない（最悪時間の）場合には定数スタックで済む。
これを実装するには、明示的なスタックを用いて非再帰（ループ）構造とするか、（末尾再帰の最適化機能があれば）要素数が多い方を末尾再帰で処理すればよい。
また、イントロソートによっても最悪 formula_7 空間を保証できる（再帰深さの閾値が formula_10 となるように設定すればよい）。
実装例.
C言語.
C言語による実装例を以下に示す：
 * 値を交換する
 * @param x - 交換するデータのポインタ
 * @param y - 交換するデータのポインタ
 * @param sz - データサイズ
void
swap(
 void* x, 
 void* y, 
 size_t sz
 char* a = x;
 char* b = y;
 while (sz > 0) {
 char t = *a;
 *a++ = *b;
 *b++ = t;
 sz--;
/** 分割関数
 * 配列をピボットによって分割し、分割位置を返す。
 * @param a - 分割する配列
 * @param cmp - 比較関数へのポインタ
 * @param sz - データサイズ
 * @param n - 要素数
 * @returns 分割位置を示すポインタ
void* 
partition(
 void* a,
 int (*cmp)(void const*, void const*),
 size_t sz,
 size_t n
 // void* に対して直接ポインタ演算はできないので予め char* へ変換する
 char* const base = a;
 if (n <= 1) return base + sz;
 char* lo = base;
 char* hi = &base[sz * (n - 1)];
 char* m = lo + sz * ((hi - lo) / sz / 2);
 // m が median-of-3 を指すようソート
 if (cmp(lo, m) > 0) {
 swap(lo, m, sz);
 if (cmp(m, hi) > 0) {
 swap(m, hi, sz);
 if (cmp(lo, m) > 0) {
 swap(lo, m, sz);
 while (1) {
 while (cmp(lo, m) < 0) lo += sz; // ピボット以上の要素を下から探す
 while (cmp(m, hi) < 0) hi -= sz; // ピボット以下の要素を上から探す
 if (lo >= hi) return hi + sz;
 swap(lo, hi, sz);
 // ピボットがスワップされた場合、スワップ先を指すよう m を更新する
 if (lo == m) {
 m = hi;
 } else if (hi == m) {
 m = lo;
 lo += sz;
 hi -= sz;
/** クイックソート
 * @param a - ソートする配列
 * @param cmp - 比較関数へのポインタ
 * @param sz - データサイズ
 * @param n - 要素数
void
quicksort(
 void* a,
 int (*cmp)(void const*, void const*),
 size_t sz,
 size_t n
 if (n <= 1) return;
 char* p = partition(a, cmp, sz, n);
 char* const base = a;
 size_t n_lo = (p - base) / sz;
 size_t n_hi = (&base[sz * n] - p) / sz;
 quicksort(a, cmp, sz, n_lo); // 左側をソート
 quicksort(p, cmp, sz, n_hi); // 右側をソート
 は なら負、 ならゼロ、 なら正の整数を返す関数とする。
Scheme.
Schemeによるクイックソートの実装例を示す：
(require-extension srfi-1) ; SRFI 1 の呼び出し方は実装依存(場合によってはデフォルト)。これは Chicken Scheme の例。
 (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.
Pythonによるクイックソートの実装例を示す：
from typing import Any
from collections.abc import MutableSequence, Callable
def median3(x, y, z):
 return max(min(x, y), min(max(x, y), z))
def partition(seq: MutableSequence[Any], keyFn: Callable[[Any], Any], first: int, last: int):
 pivot = median3(keyFn(seq[first]), keyFn(seq[first + (last - first) // 2]), keyFn(seq[last]))
 while True:
 while keyFn(seq[first]) < pivot:
 first += 1
 while pivot < keyFn(seq[last]):
 last -= 1
 if first >= last:
 return last + 1
 seq[first], seq[last] = seq[last], seq[first]
 first += 1
 last -= 1
def quicksort(seq: MutableSequence[Any], keyFn: Callable[[Any], Any]):
 def quicksortImpl(seq: MutableSequence, keyFn: Callable[[Any], int], first: int, last: int):
 while first < last:
 p = partition(seq, keyFn, first, last)
 if (p - first) < (last - p):
 quicksortImpl(seq, keyFn, first, p - 1)
 first = p
 else:
 quicksortImpl(seq, keyFn, p, last)
 last = p - 1
 quicksortImpl(seq, keyFn, 0, len(seq) - 1)
外部リンク.
[[Category:ソート]]