クイックソート (Quick Sort)

クイックソートは高速で効率的なソートアルゴリズムで、多くのプログラミング言語の標準ライブラリで採用されています。1960年にイギリスのコンピュータ科学者トニー・ホーア（Tony Hoare）によって開発されました。「分割統治法（Divide and Conquer）」の代表的な例として知られています。

1. アルゴリズムの基本原理

クイックソートの基本的な仕組みは以下のようになります。

ピボット選択：配列から1つの要素（ピボット）を選ぶ
パーティション：ピボットより小さい要素を左側に、大きい要素を右側に移動させる
再帰的処理：左側と右側のサブ配列に対して、同じ処理を再帰的に適用する

この3つのステップを繰り返すことで、最終的に配列全体がソートされます。

2. 詳細なアルゴリズムの流れ

2.1 ピボットの選択

ピボットの選び方にはいくつかの方法があります。

最後の要素：単純ですが、既にソートされた配列では効率が悪くなる可能性があります
最初の要素：同様に単純ですが、同じ問題があります
ランダムな要素：最悪のケースを回避できる確率が高くなります
中央値：配列の最初、真ん中、最後の要素の中央値を選ぶ方法（「中央値の3つ組」）

2.2 パーティション処理

パーティション処理は、クイックソートの核心部分です。一般的なパーティションアルゴリズム（Lomutoのパーティション）は以下のように動作します。

ピボットを選ぶ（例：配列の最後の要素）
左側のポインタ i を初期位置（インデックス -1）に設定
配列を左から右へ走査していき、各要素とピボットを比較
- 要素がピボット以下の場合：i を1増やし、現在の要素と i の位置の要素を交換
- 要素がピボットより大きい場合：何もしない
走査が終わったら、i+1 の位置とピボットの位置を交換

これにより、ピボット未満の要素は左側に、ピボットより大きい要素は右側に配置されます。

2.3 再帰的処理

パーティション処理によって、ピボットは最終的な位置に配置されました。次に、ピボットの左側と右側のサブ配列に対して同じ処理を再帰的に適用します。

quickSort(arr, low, high):
    if (low < high):
        pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)  // 左側のサブ配列をソート
        quickSort(arr, pivotIndex + 1, high)  // 右側のサブ配列をソート

再帰は、サブ配列のサイズが1以下になった時点で終了します。

3. クイックソートの特性

3.1 時間計算量

最良の場合：O(n log n) – 各パーティションがほぼ等しいサイズに分割される場合
平均の場合：O(n log n)
最悪の場合：O(n²) – すでにソートされている配列や、すべての要素が同じ値の配列

ただし、ランダムなピボット選択や「中央値の3つ組」を使用することで、最悪のケースを回避できることが多いです。

3.2 空間計算量

再帰による空間計算量：O(log n) – 平均の場合
最悪の場合：O(n) – 不均衡な分割が連続する場合

3.3 特徴

安定性：クイックソートは一般的に「不安定」なソートです（同じ値を持つ要素の相対的な順序が保存されない）
適応性：部分的にソートされたデータに対しても効率はあまり変わりません
実装の容易さ：基本的な実装は比較的シンプルです
インプレース性：追加の配列を必要とせず、元の配列内でソートできます（O(log n)のスタック空間を除く）

4. クイックソートの最適化

4.1 小さな配列に対する挿入ソートの使用

配列のサイズが小さい場合（一般的に10〜20要素以下）、挿入ソートの方が効率的なことがあります。

if (high - low < CUTOFF):
    insertionSort(arr, low, high)
    return

4.2 3-wayクイックソート（Dutch national flag問題）

多くの重複要素がある場合、「3-wayクイックソート」が効果的です。

ピボットより小さい要素
ピボットと等しい要素
ピボットより大きい要素

これにより、重複要素が多い配列でのパフォーマンスが向上します。

4.3 テール再帰の最適化

再帰の深さを減らすために、小さい方のサブ配列を先に処理し、大きい方のサブ配列に対してはループを使用する最適化があります。

while (low < high):
    // パーティション処理
    if (pivotIndex - low < high - pivotIndex):
        quickSort(arr, low, pivotIndex - 1)
        low = pivotIndex + 1
    else:
        quickSort(arr, pivotIndex + 1, high)
        high = pivotIndex - 1

5. クイックソートと他のソートアルゴリズムの比較

5.1 マージソートとの比較

メモリ使用：マージソートはO(n)の追加メモリを必要とするが、クイックソートはほぼインプレース
安定性：マージソートは安定、クイックソートは不安定
最悪の場合の計算量：マージソートはO(n log n)、クイックソートはO(n²)
キャッシュ効率：クイックソートはローカリティが良いため、多くの場合実際のパフォーマンスが高い

5.2 ヒープソートとの比較

最悪の場合の計算量：ヒープソートはO(n log n)
空間計算量：両方ともインプレース
実際のパフォーマンス：一般的に、クイックソートの方が定数因子が小さく、実際のパフォーマンスが良い

6. 実装例（JavaScript）

以下は、JavaScriptでのクイックソートの基本的な実装例です：

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // パーティション処理を行い、ピボットのインデックスを取得
    const pivotIndex = partition(arr, low, high);
    
    // ピボットの左側をソート
    quickSort(arr, low, pivotIndex - 1);
    
    // ピボットの右側をソート
    quickSort(arr, pivotIndex + 1, high);
  }
  
  return arr;
}

function partition(arr, low, high) {
  // 最後の要素をピボットとして選択
  const pivot = arr[high];
  
  // 小さい要素を配置するインデックス
  let i = low - 1;
  
  // 配列を走査し、ピボット以下の要素を左側に移動
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      // 交換
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  // ピボットを正しい位置に配置
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  
  // ピボットの最終位置を返す
  return i + 1;
}

// 使用例
const array = [10, 7, 8, 9, 1, 5];
console.log(quickSort(array)); // [1, 5, 7, 8, 9, 10]