クイックセレクト
クイックソートでは、線形時間で配列(インデックスの left から right への範囲)を特定の要素(ピボット)より小さい要素の部分配列と等しいかより大きい要素の部分配列へ分割し(partition)、部分配列にも繰り返し分割処理を行うことで目的の配列を整列させる。例えば要素 list[pivotIndex] をピボットとしてパーティションを実行する擬似コードは次のとおり:
これはロムトの分割法として知られている。ロムトの方法は、ホーアの分割法よりも要素の交換(swap)を行う回数が多くなるため、一般にはホーアの方法がより高速であると考えられている。しかし、投機的実行を考慮すると実際にはロムトの方法がホーアの方法より速くなる場合がある。 また、ホーアの方法は双方向イテレータを要求するが、ロムトの方法は前方イテレータのみを要求するという違いがある(例えば片方向リストのソート)。
クイックソートでは、分割後の両方の範囲を再帰処理するため最良の時間計算量は Ω ( n log  n ) {\displaystyle \Omega (n\log n)} である。しかし選択アルゴリズムでは、目的の要素がピボットより後ろにあるか前にあるかは事前に分かるため、ソートと異なり片方の範囲のみを再帰呼び出しをすることで、最終的に目的の要素を正しい位置に置くことができる。これがクイックセレクトである。
クイックセレクトは線形時間で終わることが期待される優れたパフォーマンスのアルゴリズムである。クイックセレクトはインプレースアルゴリズムでもあり、末尾呼び出し最適化がかかる場合や、以下のようにループで末尾再帰を排除した実装を行う場合は、定数のメモリ空間で実行できる。
ほとんど確実に線形時間で処理をする簡単な解決策は、ランダムにピボットを選択することである。
決定的な手法としては、クイックソートのように3要素(例えば、先頭・中央・末尾)の中央値をピボットに選ぶ戦略が有効である。これにより、現実でよくある部分的にソートされたデータに対して線形のパフォーマンスが得られる。ただし、不自然な並びでは依然として最悪計算量になる可能性がある。 David Musser(英語版)は、その戦略に対する攻撃を可能にする「3要素の中央値キラー」シーケンスについて説明している。彼はこれを動機としてイントロセレクト(英語版)を開発した。
より洗練されたピボット戦略を使用することで、最悪の場合でも線形パフォーマンスを保証できる。これを実現できるのが中央値の中央値だが、ピボットの計算のオーバーヘッドは高いため、実際にはあまり使用されない。