クイックソートのピボット選択戦略

クイックソートの動作原理

クイックソートは実際に最も広く使用されている汎用ソートアルゴリズムです。ピボット要素を選択し、ピボットより小さいすべての要素が前に、大きいすべての要素が後に来るように配列をパーティションします。

Lomutoパーティション方式

function partition(arr, low, high):
  pivot = arr[high]  // 末尾要素をピボットに
  i = low - 1
  for j = low to high - 1:
    if arr[j] < pivot:
      i++
      swap(arr[i], arr[j])
  swap(arr[i+1], arr[high])
  return i + 1

ピボット選択戦略

ピボットの選択はクイックソートの性能に劇的に影響します：

戦略	最良ケース	最悪ケース	備考
末尾要素	O(n log n)	O(n²)	ソート済み入力で劣化
先頭要素	O(n log n)	O(n²)	末尾要素と同じ問題
ランダム	O(n log n)期待値	O(n²)稀	良い実用的選択
三数の中央値	O(n log n)	O(n²)非常に稀	最良の実用的選択

三数の中央値

三数の中央値戦略は、先頭、中間、末尾の要素の中央値をピボットとして選びます。配列 [8, 2, 5, 1, 9] の場合：

• 先頭 = 8、中間 = 5、末尾 = 9
• 中央値 = 8
• ソート済みおよび逆順入力での最悪ケースを回避

クイックソートが実際に速い理由

O(n²)の最悪ケースにもかかわらず、クイックソートは通常マージソートより高速です：

1. キャッシュ局所性: 要素は同じ配列領域内で比較・スワップされる
2. 追加メモリなし: インプレースパーティションにより割り当てオーバーヘッドなし
3. 小さな定数係数: 内部ループがタイト — 比較と条件付きスワップのみ
4. 末尾呼び出し最適化: 小さいパーティションを末尾再帰で処理可能

Introsort：本番環境のクイックソート

現代のC++やRustの標準ライブラリはIntrosortを使用しています。クイックソートで開始し、再帰深度が2 * log nを超えるとヒープソートに切り替え、O(n log n)の最悪ケース保証を維持しながらクイックソートの実用的な速度を保ちます。