クイックソートとは？ わかりやすく解説

${\displaystyle O(n^{2})}$

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

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

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

最悪計算量の回避

時間計算量

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

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

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

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

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

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

空間計算量

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

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

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

また、イントロソートによっても最悪 ${\displaystyle O(\log n)}$ 空間を保証できる（再帰深さの閾値が ${\displaystyle \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
                                  ;; 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
# 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言語のコードで紹介．

ウィキペディア小見出し辞書

索引トップ 用語の索引 ランキング