クイックソート

クイックソートは基準値（ピボット）を選び、配列を「ピボット未満」と「ピボット以上」に分けます。その後、両側を再帰的に整列します。平均時間計算量は O(n log n) です。分割は元の配列内で行いますが、偏った分割が続くと O(n²) に退化します。

ピボットの役割は境界を決めることです。走査中に小さい値を左へ集め、最後にピボットを両領域の間へ移します。この位置は確定するので、次は左右の区間だけを処理します。

クイックソートの分割

このレッスンは Lomuto 分割を使い、区間末尾の arr[hi] をピボットに選びます。j は lo から hi − 1 まで走査します。i は、ピボット未満の領域の次の位置を指します。

arr[j] < pivot なら arr[j] と arr[i] を交換し、i を一つ進めます。arr[j] >= pivot なら i を動かさず、j だけを進めます。走査が終わると、i より左はピボット未満、i から hi − 1 まではピボット以上です。

最後に arr[i] と arr[hi] を交換します。partition が返す位置 p にピボットが収まり、arr[lo..p−1] と arr[p+1..hi] を再帰処理します。どちらにも p は含めません。

比較は厳密な < です。同値の要素は右側に残ります。離れた位置との交換は、同値の要素の順序を変えることがあります。クイックソートは安定ではありません。

クイックソートのステップ

初期入力は [38, 12, 56, 7, 12, 41, 23] です。元の添字 1 の 12 を 12a、添字 4 の 12 を 12b と呼び、同値の要素を区別します。

最初の分割：[0..6]、ピボットは 23。 38 は 23 以上なので残します。12a は添字 0 と交換し、i を 1 に進めます。56 は残し、7 を添字 1、12b を添字 2 へ交換します。41 は残します。最後に 23 を添字 3 へ移すと、[12a, 7, 12b, 23, 56, 41, 38] になります。添字 3 は確定です。

左側の分割：[0..2]、ピボットは 12b。 12a は同値なので < を満たしません。7 を添字 0 と交換すると [7, 12a, 12b] になります。最後のピボット交換で [7, 12b, 12a] となり、二つの 12 の順序が逆転します。値は昇順でも、元の順序は保持されません。

[0..0] と [2..2] は要素が一つなので終了します。右側 [4..6] の [56, 41, 38] では、ピボット 38 が添字 4 に入り、[38, 41, 56] になります。残る [5..6] のピボット 56 は移動不要です。結果は [7, 12b, 12a, 23, 38, 41, 56] です。

アニメーション下部の帯は、分割中の領域を示します。左側は < pivot、中央は走査済みの >= pivot、残りは未確認です。ピボットが緑色になると、その位置が確定します。

時間・空間計算量

分割がほぼ半分なら、再帰の深さは約 log n、各深さで走査する要素の合計は O(n) です。ピボットが毎回最小値か最大値なら、一回で一要素しか確定せず、深さは n に近づきます。

この実装は末尾の値を選ぶため、整列済みの入力でも最悪の場合になります。ランダムなピボットや三数の中央値は、偏りが続く可能性を減らしますが、最悪時間は O(n²) です。分割が配列内で済んでも、再帰スタックを含む追加領域は O(1) ではありません。

境界条件

• 空区間・一要素の区間：処理を終えます。ピボットが端に入る場合も空区間ができます。
• 昇順・降順：末尾が極値になり、分割が偏り続けます。時間は O(n²) です。
• 重複値：値は整列しますが、同値の順序は保証しません。初期入力の二つの 12 が例です。
• 全要素が同値：すべて >= pivot 側に残り、一回でピボット一つだけが確定します。この Lomuto 分割では二乗時間になります。

よくある間違い

• 再帰区間に p を含める：[lo..p] や [p..hi] では区間が縮まず、再帰が終了しない場合があります。
• 最後のピボット交換を省く：返す添字とピボットの位置が一致しません。
• 比較のたびに i を進める：i は小さい値を受け入れたときだけ進みます。
• < を無条件に <= へ変える：同値が左側に入り、分割結果と偏る方向が変わります。
• 昇順なら安定だと考える：安定性は同値の要素の順序です。順序の保持が必要なら、マージソートなどを選びます。