クイックセレクト

クイックセレクトは、配列内でk番目に小さい要素を特定するための選択アルゴリズムです。クイックソートと密接な関係があり、同じくアントニー・ホーアによって考案されたため、ホーアの選択アルゴリズムとも呼ばれます。クイックソートと同様に、平均的なパフォーマンスは優れていますが、最悪の場合のパフォーマンスは低下します。効率的な実装が可能なため、クイックセレクトとその派生アルゴリズムは、選択アルゴリズムとして広く利用されています。

アルゴリズムの概要

クイックセレクトは、クイックソートと同様に、まず配列からピボットとなる要素を一つ選択します。次に、このピボットを基準にして、配列内の要素をピボットより小さい要素と大きい要素の二つのグループに分割します。この分割操作を再帰的に繰り返しますが、クイックソートとは異なり、クイックセレクトでは、目的の要素が含まれる一方のグループのみを再帰的に処理します。このアプローチにより、平均計算量を大幅に削減することができます。

クイックソートの平均計算量が\( \Theta(n \log n) \)であるのに対し、クイックセレクトの平均計算量は\( \Theta(n) \)となります。ただし、最悪の場合の計算量はクイックソートと同じく\( O(n^2) \)となります。

クイックセレクトは通常、インプレースアルゴリズムとして実装されます。これは、追加のメモリをほとんど必要とせず、配列内での要素の交換によって処理を行うことを意味します。また、k番目の要素を選択するだけでなく、配列を部分的にソートする効果もあります。選択アルゴリズムとソートの関係については、関連資料を参照してください。

アルゴリズムの詳細

クイックソートでは、配列をピボット要素を基準に二分割する分割処理（partition）を繰り返し行い、配列全体を整列させます。具体的には、以下の手順で分割処理が行われます。

function partition(list, left, right, pivotIndex) is
pivotValue := list[pivotIndex]
swap list[pivotIndex] and list[right] // ピボットを末尾に移動
storeIndex := left
for i from left to right - 1 do
if list[i] < pivotValue then
swap list[storeIndex] and list[i]
increment storeIndex
swap list[right] and list[storeIndex] // ピボットを正しい位置に戻す
return storeIndex

これはロムトの分割法と呼ばれ、ホーアの分割法よりも要素の交換回数が多くなる傾向があります。一般的にはホーアの分割法がより高速であると考えられていますが、投機的実行を考慮すると、ロムトの方法が有利な場合もあります。また、ロムトの分割法は前方イテレータのみを必要とするため、片方向リストなどにも適用できます。

クイックソートでは分割された両方の範囲を再帰的に処理しますが、クイックセレクトでは、目的の要素がピボットの前にあるか後ろにあるかによって、片方の範囲のみを再帰的に処理します。これにより、最終的に目的の要素を正しい位置に特定できます。以下がクイックセレクトの基本的なアルゴリズムです。

function select(list, left, right, k) is
if left = right then // 残りの要素が一つなら
return list[left] // その要素を返す
pivotIndex := ... // leftとrightの間からピボットを選択
pivotIndex := partition(list, left, right, pivotIndex)
// ピボットは分割処理後の位置にある
if k = pivotIndex then
return list[k]
else if k < pivotIndex then
return select(list, left, pivotIndex - 1, k)
else
return select(list, pivotIndex + 1, right, k)

クイックセレクトは、線形時間で処理が完了することが期待される効率的なアルゴリズムです。また、インプレースアルゴリズムであり、末尾呼び出し最適化やループによる末尾再帰の排除を行うことで、定数メモリ空間で実行できます。

時間計算量

クイックセレクトの平均的なパフォーマンスは、ピボットの選択に大きく依存します。適切なピボットが選択され、検索範囲が一定の割合で減少する場合、計算時間は線形時間\( O(n) \)となります。しかし、毎回検索範囲がわずかしか減少しないような不適切なピボットが選ばれ続けると、最悪の場合には\( O(n^2) \)の計算時間が必要になります。例えば、ソート済みの配列に対して、常に最大要素をピボットとして選ぶような実装がこれに該当します。しかし、ランダムにピボットを選ぶことで、最悪ケースが発生する確率は指数関数的に減少し、実用上はほぼ確実に線形時間で処理が完了します。

派生アルゴリズム

ランダムピボット: ランダムにピボットを選択することで、ほとんど確実に線形時間で処理が完了します。
中央値ピボット: 先頭、中央、末尾の3要素の中央値をピボットに選ぶ戦略は、現実世界でよくある部分的にソートされたデータに対して高いパフォーマンスを発揮します。
イントロセレクト: クイックセレクトを基本とし、処理が一定回数で終わらない場合に、中央値の中央値アルゴリズムに切り替えることで、高速な平均性能と線形時間での最悪ケースパフォーマンスを両立します。
フロイド・リベストのアルゴリズム: より複雑なピボット戦略を用いることで、さらなる性能改善を図ります。

計算量の詳細

平均時間計算量は、中央値の場合で\( 3.4n \)以下とされています。フロイド・リベストのアルゴリズムを用いると、\( 1.5n + \Theta(n^{1/2}) \)まで改善されます。