クイックソートの仕組み・コード・計算量をわかりやすく解説

考え方を平易に説明

1. ピボットとなる要素を選びます。たとえば最後の要素やランダムな要素です。
2. パーティション：ピボットより小さい要素をすべてその左に、大きい要素をすべてその右に移動します。これでピボットは、ソート後の最終位置に収まります。
3. ピボットの左側の部分と右側の部分を、それぞれ再帰的にソートします。その後に結合する作業は必要ありません。

マージソートは分割が簡単でマージが難しいアルゴリズムです。クイックソートはその逆で、パーティションが仕事をし、2つの半分は同じ配列内ですでに正しい位置にあるため、結合は不要です。

具体例：ロムートのパーティション1回分

[10, 80, 30, 90, 40, 50, 70] を、最後の要素 70 をピボットとしてパーティションします。インデックス i はピボットより小さい要素の領域の終端を示し、j は左から右へ走査します。

70 はインデックス 4、つまり最終位置に収まりました。クイックソートは次に、[10, 30, 40, 50] と [90, 80] を別々にソートします。

Pythonでの実装

import random

def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]       # move the pivot to the end
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo=0, hi=None):
    """Sort list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:           # recurse on the smaller side
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1
    return a

print(quicksort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]
print(quicksort([3, 3, 3, 1]))                   # [1, 3, 3, 3]

小さいほうの側に再帰し、大きいほうの側はループで処理すると、最悪ケースでもスタックの深さを O(log n) に抑えられます。アイデアの説明には、インプレースではない短い版がよく使われますが、これは各段階で新しいリストを確保します。

def quicksort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort_simple(less) + equal + quicksort_simple(greater)

print(quicksort_simple([5, 2, 9, 2, 7]))   # [2, 2, 5, 7, 9]

時間計算量と空間計算量

典型的な最悪ケースは、すでにソート済みまたは逆順にソート済みの入力に対して、先頭または末尾の要素を固定でピボットにする場合です。各パーティションがピボットしか取り除かないので、O(n) の作業が n 段階続きます。ランダムなピボットなら、どんな入力でもこれが起こる可能性は極めて低くなります。

クイックソートと他のソートの比較

クイックソートは安定ではありません。パーティション中の交換で、要素が等しい要素を飛び越えることがあるためです。メモリ上の配列では、内側のループが単純で、インプレースで動作し、メモリにほぼ順番にアクセスするため、通常はマージソートやヒープソートに勝ります。C++ の標準ライブラリの多くの std::sort 実装で使われているイントロソートは、クイックソートで始めて、再帰が深くなりすぎるとヒープソートに切り替えることで、O(n log n) を保証します。

ピボットの選び方、派生、よくある間違い

• ピボットの選び方：先頭または末尾の要素（簡単ですが、ソート済みの入力で O(n²) になります）、ランダムな要素、三点中央値（先頭・中央・末尾の中央値）。
• ホーアのパーティション：2つのインデックスが互いに向かって動き、逆側にあるペアを交換します。平均では、ロムートより交換が少なくなります。
• 三分割パーティション（オランダ国旗問題）：小さい・等しい・大きいの3つに分けます。キーの重複が多い配列でも高速になります。単純なロムート方式は、すべてのキーが等しいと O(n²) に悪化します。
• デュアルピボットクイックソートは、2つのピボットと3つの部分を使います。Javaは、プリミティブ型の配列のソートにこれを使っています。
• クイックセレクトは、パーティションを1回行って片側にだけ再帰し、k 番目に小さい要素を平均 O(n) 時間で見つけます。

クイックソートを使う場面

安定性が不要で、メモリ上の配列をソートする場合、クイックソートは良いデフォルトの選択です。ただしPythonでは、代わりに sorted() か list.sort() を使ってください。これらは Timsort を使っており、安定で、部分的にソート済みのデータでも高速です。クイックソートの実装は面接で非常によく出る課題で、最悪ケース、ピボットの選び方、安定性、クイックセレクトによる k 番目に大きい要素の探索などの質問が続くことがよくあります。