クイックソート

クイックソート#

クイックソート（quick sort） は分割統治法を使うソートアルゴリズム。ピボット（基準値）を選び、ピボットより小さい要素と大きい要素に分割して再帰的にソートする。平均的に最速のソートアルゴリズムの一つ。

計算量

最悪時間計算量

\(O(n^2)\)（ピボット選択が偏る場合）

平均時間計算量

\(O(n \log n)\)

最良時間計算量

\(O(n \log n)\)

空間計算量

\(O(\log n)\)（再帰スタック）

特徴

  • 非安定ソート（実装による）

  • in-place（補助配列不要）

  • 定数係数が小さく、キャッシュ効率が良いため実用上高速

  • ピボット選択がパフォーマンスの鍵

アルゴリズム#

quick_sort(arr, lo, hi):
    if lo >= hi: return
    p = partition(arr, lo, hi)  # ピボットの最終位置を返す
    quick_sort(arr, lo, p - 1)
    quick_sort(arr, p + 1, hi)

Lomuto分割法: 末尾をピボットにし、左から走査する。シンプルだが定数係数が若干大きい。

Hoare分割法: 両端から走査。実際には交換回数が少なく速い。

def quick_sort(arr: list) -> list:
    """シンプルな実装（Lomuto 分割、新規リスト版）"""
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 中央値をピボットに
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

import random

data = [10, 7, 8, 9, 1, 5]
print("入力:", data)
print("出力:", quick_sort(data))

random.seed(3)
large = random.sample(range(10000), 100)
assert quick_sort(large) == sorted(large)
print("ランダム100件: OK")

入力: [10, 7, 8, 9, 1, 5]
出力: [1, 5, 7, 8, 9, 10]
ランダム100件: OK

in-place 実装（Lomuto 分割法）#

def quick_sort_inplace(arr: list) -> list:
    a = arr.copy()
    _qs(a, 0, len(a) - 1)
    return a

def _qs(a: list, lo: int, hi: int) -> None:
    if lo >= hi:
        return
    p = _partition(a, lo, hi)
    _qs(a, lo, p - 1)
    _qs(a, p + 1, hi)

def _partition(a: list, lo: int, hi: int) -> int:
    # 末尾・先頭・中央の中央値をピボットに（median-of-3）
    mid = (lo + hi) // 2
    candidates = [(a[lo], lo), (a[mid], mid), (a[hi], hi)]
    candidates.sort()
    _, pivot_idx = candidates[1]
    a[pivot_idx], a[hi] = a[hi], a[pivot_idx]
    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

data = [10, 7, 8, 9, 1, 5]
print(quick_sort_inplace(data))
assert quick_sort_inplace(data) == sorted(data)

[1, 5, 7, 8, 9, 10]

最悪ケース（ナイーブ実装での注意）#

常に最大・最小をピボットに選ぶと、分割が \(n-1\) と \(0\) になり \(O(n^2)\) に退化する。例えば既ソート済み配列に末尾ピボットを適用した場合が該当する。

対策:

  • ランダムピボット: random.choice でピボットを選ぶ

  • Median-of-3: 先頭・中央・末尾の中央値をピボットに（上記の _partition 参照）

  • イントロソート: 再帰深度が \(\log n\) を超えたらヒープソートに切り替える（C++ STL の std::sort）

import random

def quick_sort_random(arr: list) -> list:
    """ランダムピボットによるクイックソート"""
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort_random(left) + mid + quick_sort_random(right)

# 既ソート済みデータでも高速
sorted_data = list(range(200))
random.seed(42)
assert quick_sort_random(sorted_data) == sorted_data
print("既ソート済み200件: OK")

既ソート済み200件: OK
Contents