クイックソート

クイックソート

クイックソートのアニメーション
クラス	ソート
最悪計算時間	$O(n^{2})$
最良計算時間	$O(n\log n)$
平均計算時間	$O(n\log n)$
最悪空間計算量	$O(n)$（素朴な実装） $O(\log n)$(Hoare 1962)

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

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

アルゴリズム

クイックソートは以下の手順で行われる。

1. ピボットの選択：適当な値（ピボットという）を境界値として選択する
2. 配列の分割：ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
3. 再帰：分割された区間に対し、再びピボットの選択と分割を行う
4. ソート終了：分割区間が整列済みなら再帰を打ち切る

配列の分割方法の一例として、以下のようなものが考えられる：

1. 配列要素からピボット P を選ぶ（ピボットの選び方については#最悪計算量の回避で詳述）
2. 配列の先頭（左側）から順に、値が P 以上の要素を探索してその位置 LO を記憶する
3. 配列の終端（右側）から逆順に、値が P 未満の要素を探索してその位置 HI を記憶する
4. LO, HI について：
   • LO が HI より左にあるなら、LO にある要素と HI にある要素の位置を入れ替え、それぞれ LO, HI の次の要素から手順 2, 3 の探索を再開する
   • そうでない場合（LO が HI より右か同じ位置にあるなら）、HI を境界として配列を分割する

分割後の要素数が一定の閾値を下回ったら挿入ソートのような「少数の要素に対してより効率的なソート」に切り替える、という手法がある。また、配列の分割方法自体にも様々な変種がある（同時に2つのピボットを選択して3分割する Dual-pivot Quicksort など）。

アルゴリズムの動作例

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

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

初期データ: 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

最悪計算量の回避

時間計算量

クイックソートの効率は配列の分割の効率に左右される。再帰の各段階で常に均等に分割される場合が最良であり、時間計算量は $O(n\log n)$ となる。一方で、常に「1要素と残り全部」のように偏って分割された場合が最悪のケースで、時間計算量が $O(n^{2})$ に悪化する。

最悪ケースを避けるにはピボットの選択に注意を払う必要がある。たとえば、既にソートされた配列に対して先頭や末尾の要素をピボットとすると最悪ケースとなる。なるべく配列の中央値をピボットとして選べるようにすれば、このようなケースを回避できる。

代表的なピボット選択の戦略として、以下のようなものが挙げられる：

• 配列の一部の要素を選び、それらの中央値を選ぶ（典型的には、配列の先頭・中間・末尾の3要素の中央値）
• ランダムに配列要素を選ぶ（真の乱数による配列選択を仮定すれば、人為的に最悪ケースを与えることが不可能になる）

また、ピボットを選ぶ前に配列をランダムに並べ替えるなどの手法によっても、ソートに最悪計算時間を要する可能性を抑えられる。

ただし、いずれの場合も最悪ケースの可能性を完全に排除できるものではない。これに対する根本的な改良として、一定の閾値よりも再帰が深くなったらヒープソートのような $O(n\log n)$ 時間が保証されるアルゴリズムに切り替える方法がある（イントロソート）。

空間計算量

分割の操作自体は追加の領域を必要としないが、再帰によるコールスタックの消費が空間計算量となる。スタックの消費は平均的には $O(\log n)$ となるが、最悪ケースでは $O(n)$ に増大するため、大きなサイズの配列の場合スタックオーバーフローを起こす危険性がある。

対策として、「分割された配列のうち、要素数が少ない方を常に先に処理する」ことで、空間計算量を最悪 $O(\log n)$ に抑えられる。このようにすると、常に均等に分割される（最良時間の）場合に $\log n$ スタックとなる一方で、1要素ずつしか分割されない（最悪時間の）場合には定数スタックで済む。

これを実装するには、明示的なスタックを用いて非再帰（ループ）構造とするか、（末尾再帰の最適化機能があれば）要素数が多い方を末尾再帰で処理すればよい。

また、イントロソートによっても最悪 $O(\log n)$ 空間を保証できる（再帰深さの閾値が $\log n$ となるように設定すればよい）。

実装例

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); // 右側をソート
}

cmp(x, y) は x < y なら負、x = y ならゼロ、x > y なら正の整数を返す関数とする。

Scheme

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
                                  ;; https://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
# median-of-three
# 与えられた3値の中央値を返す
def median3(x, y, z):
    return max(min(x, y), min(max(x, y), z))

# 分割関数
# 配列の指定範囲をピボットに従って分割する
# 
# @param seq   - 分割する配列
# @param keyFn - 配列要素のキー値を計算する関数
# @param first - 分割範囲の最初のインデックス
# @param last  - 分割範囲の最後のインデックス
# @returns 分割点のインデックス
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

# クイックソート
#
# @param seq   - ソートする配列
# @param keyFn - 配列要素のキー値を計算する関数
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)

関連項目

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

参考文献

• Hoare, C. A. R. (1962). “Quicksort”. The Computer Journal 5 (1): 11. doi:10.1093/comjnl/5.1.10. 
• Skiena, Steven S. (2008). The Algorithm Design Manual. Springer. p. 129. ISBN 978-1-84800-069-8 
• Yaroslavskiy, Vladimir (2009年). “Dual-Pivot Quicksort”. 2015年10月2日時点のオリジナルよりアーカイブ。2021年8月2日閲覧。
• Sedgewick, Robert『アルゴリズムC 第1～4部: 基礎・データ構造・整列・探索』近代科学社、2018年2月28日（原著1998年9月1日）、273-291頁。ISBN 978-47-649-0560-3。 
• Sedgewick, Robert; Wayne, Kevin (2011-03-19). Algorithms (4th ed.). Addison-Wesley. p. 295. ASIN 032157351X. ISBN 0-321-57351-X. NCID BB06083373. LCCN 2011-707. OCLC 951241174 
• 杉山, 行浩『Cで学ぶデータ構造とアルゴリズム』東京電機大学出版局、1995年、159頁。ISBN 978-45-015-2380-0。 

外部リンク

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