クイック選択

クイック選択

クイック選択アルゴリズムのアニメーションによる視覚化。22 番目に小さい値を選択します。
クラス	選択アルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O}$（２）​
最高の パフォーマンス	${\displaystyle O}$名詞​​
平均的 なパフォーマンス	${\displaystyle O}$名詞​​
最悪の場合の 空間複雑度	${\displaystyle O}$（１）

コンピュータサイエンスにおいて、クイックセレクトは、順序なしリストのk番目に小さい要素を見つける選択アルゴリズムであり、 k番目の順序統計量とも呼ばれます。関連するクイックソートソートアルゴリズムと同様に、トニー・ホーアによって開発されたため、ホーアの選択アルゴリズムとも呼ばれます。^[1]クイックソートと同様に、実際には効率的で、平均的なケースでは優れたパフォーマンスを発揮しますが、最悪のケースではパフォーマンスが低下します。クイックセレクトとそのバリアントは、効率的な実際の実装で最もよく使用される選択アルゴリズムです。

クイックセレクトは、クイックソートと同じ全体的なアプローチを使用して、1 つの要素をピボットとして選択し、ピボットに基づいてデータを 2 つに分割します (ピボットより小さいか大きいかに応じて分割します)。ただし、クイックソートのように両側に再帰するのではなく、クイックセレクトは片側 (検索する要素がある側) のみに再帰します。これにより、平均複雑度が から に削減され、最悪の場合 になります。 ${\displaystyle O(n\log n)}$${\displaystyle O(n)}$${\displaystyle O(n^{2})}$

クイックソートと同様に、クイックセレクトは一般にインプレース アルゴリズムとして実装され、k番目の要素を選択するだけでなく、データを部分的にソートします。ソートとの関連の詳細については、 選択アルゴリズムを参照してください。

クイックソートには、 と呼ばれるサブプロシージャがありpartition、線形時間でリスト (インデックスから までleft)rightを 2 つの部分、つまり特定の要素より小さい部分と、要素以上の部分にグループ化できます。要素 についてパーティションを実行する疑似コードを次に示しますlist[pivotIndex]。

関数partition(list, left, right, pivotIndex)は
    ピボット値 := リスト[ピボットインデックス]
    list[pivotIndex]とlist[right]を入れ替える  // ピボットを末尾に移動する
    ストアインデックス:=左
    左から右へi − 1の場合、 list[i] < pivotValueならば
        
            list[storeIndex]とlist[i]を入れ替える
            ストアインデックスを増分する
    list[right]とlist[storeIndex]を入れ替える  // ピボットを最終位置へ移動する
    return storeIndex

これはロミュート分割方式として知られており、ホアのオリジナルの分割方式よりも単純ですが、効率は劣ります。

クイックソートでは、両方のブランチを再帰的にソートし、最速のケース時間を実現します。ただし、選択を行うときは、ピボットが最終的なソート位置にあり、その前の要素はすべてソートされていない順序で、ピボットの後の要素はすべてソートされていない順序で並んでいるため、目的の要素がどのパーティションにあるかは既にわかっています。したがって、1 回の再帰呼び出しで、目的の要素を正しいパーティションに見つけ、これを基にクイック選択を行います。 ${\displaystyle O(n\log n)}$

// left..right の範囲内でリストの k 番目に小さい要素を返します
// (つまり left <= k <= right)。
function select(list, left, right, k)は、if left = right thenです
    // リストに要素が 1 つしか含まれていない場合は、 list[left]  を返します// その要素を返します
    pivotIndex := ...      // left と right の間の pivotIndex を選択します// たとえば、 left + floor(rand() % (right − left + 1))   
        
                           
    pivotIndex := パーティション(リスト、左、右、pivotIndex)
    // ピボットは最終的なソート位置にあります
    。k = pivotIndexの場合は
        list[k]
    を返し、そうでない場合はk < pivotIndexの場合は
        select(list, left, pivotIndex − 1, k)
    を返し、そうでない場合は
        select(list, pivotIndex + 1, right, k) 
を返します。

クイックソートとの類似性に注目してください。最小値に基づく選択アルゴリズムが部分選択ソートであるのと同様に、これは部分クイックソートであり、そのパーティションのみを生成して分割します。この単純な手順は線形パフォーマンスが期待されており、クイックソートと同様に、実際には非常に優れたパフォーマンスを発揮します。また、これはインプレース アルゴリズムであり、末尾呼び出し最適化が利用可能な場合、またはループで 末尾再帰を排除する場合は、一定のメモリ オーバーヘッドのみを必要とします。${\displaystyle O(\log n)}$${\displaystyle O(n)}$

関数select(list, left, right, k) はループし、
     left = rightの場合はlist[left]を返します。
        
            
        pivotIndex := ...      // 左と右の間の pivotIndex を選択
        pivotIndex := パーティション(リスト、左、右、pivotIndex)
        k = pivotIndexの場合は
            list[k]
        を返し、そうでない場合はk < pivotIndexの場合は
            右 := ピボットインデックス − 1
        それ以外
            左 := ピボットインデックス + 1

クイックソートと同様に、クイックセレクトは平均して良好なパフォーマンスを発揮しますが、選択されたピボットの影響を受けます。 適切なピボット、つまり検索セットを常に一定の割合で減らすピボットが選択されると、検索セットのサイズは指数関数的に減少し、帰納法（または等比級数を合計）により、各ステップが線形で全体の時間が定数倍（検索セットがどれだけ速く減少するかによって異なります）であるため、パフォーマンスは線形であることがわかります。 ただし、毎回 1 つの要素だけ減らすなど、不適切なピボットが常に選択されると、最悪の場合のパフォーマンスは 2 乗になります。 これは、たとえば、セットの最大要素を検索し、最初の要素をピボットとして使用し、データをソートする場合に発生します。 ただし、ランダムに選択されたピボットの場合、この最悪のケースは非常にまれです。十分に大きな定数 に対して、 を超える比較を使用する確率は、 の関数として超指数的に小さくなります。^[2]${\displaystyle O(n^{2}).}$${\displaystyle Cn}$${\displaystyle C}$${\displaystyle C}$

最も簡単な解決法はランダム ピボットを選択することです。これにより、ほぼ確実に線形時間が得られます。決定論的には、(クイックソートのように) 3 の中央値ピボット戦略を使用できます。これにより、現実世界では一般的であるように、部分的にソートされたデータに対して線形パフォーマンスが得られます。ただし、人為的なシーケンスは、依然として最悪のケースの複雑さを引き起こす可能性があります。David Musser は、その戦略に対する攻撃を可能にする「3 の中央値キラー」シーケンスについて説明しており、これが彼のintroselectアルゴリズムの動機の 1 つでした。

より洗練されたピボット戦略を使用することで、最悪の場合でも線形パフォーマンスを保証できます。これは、中央値の中央値アルゴリズムで行われます。ただし、ピボットを計算するオーバーヘッドは大きいため、実際には一般的に使用されません。基本的な quickselect と中央値の中央値をフォールバックとして組み合わせて、高速な平均ケースのパフォーマンスと線形の最悪ケースのパフォーマンスの両方を得ることができます。これはintroselectで行われます。

平均時間計算量をより細かく計算すると、ランダムピボットの場合に最悪のケースが発生します（中央値の場合。他のkはより高速です）。^[3]より複雑なピボット戦略により、定数を3/2に改善することができ、フロイド-リベストアルゴリズムが生成されます。このアルゴリズムでは、中央値の場合の平均計算量は で、他のkはより高速です。 ${\displaystyle n(2+2\log 2+o(1))\leq 3.4n+o(n)}$${\displaystyle 1.5n+O(n^{1/2})}$

• フロイド・リベストアルゴリズム
• イントロセレクト
• 中央値の中央値

• 「qselect」、Matlab のクイック選択アルゴリズム、 Manolis Lourakis