選択アルゴリズム
選択アルゴリズム(英: selection algorithm)とは、数列から k 番目に小さい(あるいは k 番目に大きい)数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、k 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。k 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。
ドナルド・クヌースは、The Art of Computer Programming の中で、k 番目に小さい要素を n 個の要素から(比較だけで)選択するのに必要な比較回数の下限を論じている。最大値または最小値を求めるのに必要な比較回数の下限は n − 1 である。これを求めるために各試合で1回の比較を行うトーナメントを想定する。トーナメント優勝者以外の選手は優勝者が決定するまでに必ず1回負けているので、比較回数の下限が n − 1 となるのである。
1番目以外では話はやや複雑になる。k 番目に小さい値を求めるには少なくとも以下の回数の比較が必要である。
n − k + ∑ n + 1 − k < j ≤ n ⌈ log 2  j ⌉ {\displaystyle n-k+\sum _{n+1-k<j\leq n}\lceil {\log _{2}j}\rceil }
この下限は k=2 のとき成り立つが、さらに大きな k ではもっと複雑な下限が存在する。