選択アルゴリズム
最悪でも線形時間となる最小値・最大値を求めるアルゴリズムは自明である。2つの変数を使い、一方にはそれまでの最大値/最小値のリスト上のインデックスを格納し、もう一方にその値そのものを格納する。リストを順次見ていき、それらしい値を見つけたら変数を更新する。
このアルゴリズムは、全順序集合の有限部分集合 A(例えば、整数、実数、辞書の単語群などの部分集合)について、A に含まれない要素 x があるとき、 max  ( A ∪ { x } ) = max  ( { max  A , x } ) {\displaystyle \operatorname {\max } (A\cup \{x\})=\operatorname {\max } (\{\operatorname {\max } A,x\})} が成り立つという定理に基づいている。このとき最小値や最大値が複数個存在する可能性に注意が必要である。上記擬似コードの比較は厳密であるため、このアルゴリズムでは最小のインデックスの最小値を探し出す。厳密でない比較(≤ および ≥)を用いれば、最大のインデックスの最小値を探し出すことになる。
最大値と最小値を同時に求めたい場合、若干の改善方法としてペア単位の比較が考えられる。つまり、奇数番目と偶数番目の要素を比較し、大きい方を最大値と、小さいほうを最小値と比較するのである。別の手法として分割統治法がある。つまり、リストを半分に分け、前半と後半それぞれの最大値・最小値を求め、それらの値から全体の最大値・最小値を求める。
k 番目に大きい値を選択するための最悪でも線形時間のアルゴリズムは、少なくとも1つ存在している。これは、マヌエル・ブラム、ロバート・フロイド、Pratt、ロバート・タージャンが1973年の論文 Time bounds for selection で発表したものである。そのアルゴリズムは独自の発明部分とクイックソートで使われている技法を合わせている。
クイックソートでは、リストをある値より小さい数のリストとそれより大きい数のリストに分割するパーティションと呼ばれるサブプロシージャがあり、これは線形時間である。a[pivotIndex] という値でパーティションを行う擬似コードを以下に示す。
クイックソートでは、2つに分けたリストをそれぞれ再帰的にソートしていき、最善で Ω(n log n) の時間がかかる。しかし、選択ではどちらのパーティションに必要な値があるか分かっている。