選択アルゴリズム
要素を新たに挿入する際、その値が含まれる範囲に対応する格納場所にそれを置く。最大値や最小値を探すには、空でない格納場所を大きいほうからか小さいほうから探していき、その格納場所の中で最大値や最小値を探せばよい。一般に k 番目の要素を探すには、各格納場所に入れた要素数をカウントしておき、端からその値を加算していって k 番目を含む格納場所を探す。そして、その格納場所内の要素群から必要な要素を線形時間アルゴリズムで探し出せばよい。
h のサイズをおよそ sqrt(n) としたとき、データの分布がほぼ一様であれば、この方式による選択は O(sqrt(n)) の時間になる。しかし、データが狭い範囲に固まって出現すると(クラスタリング)、この手法では1つの格納場所に多大な要素が格納されることになってしまう(クラスタリングはハッシュ関数をうまく設定することで排除できるが、k 番目に大きい値をばらばらにハッシュされた中から探すのは現実的でない)。さらにハッシュテーブルと同様で、この方式では要素数 n が増大して h より大きくなった場合に、効率を改善するために再構成(つまり h を大きくする)する必要がある。この方式はデータ数が分かっている場合の順序統計量を探すのに適している(例えば学生の成績の統計処理など)。各格納場所の値の範囲を 1 としてそれぞれに要素数をカウントするようにするのが最も優れている。そのようなハッシュテーブルは要約統計量でデータを分類するための度数分布表に似ている。
最大値/最小値アルゴリズムをそのまま使って、k 番目に小さい値(または k番目に大きい値)を求めるアルゴリズムは簡単に作成できるが、効率は不十分である。必要な時間は O(kn) で、k が小さければ小さいほど効率が良い。このアルゴリズムでは、単に最もそれらしい値を見つけてそれをリストの先頭に移動させ、必要な k番目に達するまでそれを繰り返す。それはちょうど不完全な選択ソートと同じである。以下に小さい値を探すアルゴリズムを示す。
この方式には以下の利点がある。
j 番目に小さい値がわかっている状態では、k 番目に小さい値を求めるのにかかる時間は O(j + (k-j)) であり、k ≤ j なら O(k) となる。
線形リストデータ構造を使うことができる。一方、後述するパーティションベースの手法ではランダムアクセスを必要とする。
リストの最大値と最小値を求める機能を持つ言語は多々あるが、汎用的な選択を組み込み機能で持っている言語はほとんどない。C++ は例外的に nth_element メソッドのテンプレートを持っており、線形時間での選択が期待できることを保証している。その実装がこれまで説明したアルゴリズムを使用している可能性は高いが、規定はされていない。(ISO/IEC 14882:2003(E) と 14882:1998(E) のセクション25.3.2参照。 また、SGI STL の nth_elementを参照)
C++ では、partial_sort アルゴリズムも提供されており、k 個の最小要素をソートした状態で選択する処理を O(nlog k) の時間で行う。k 個の最大要素を選択するアルゴリズムは提供されていないが、順序判定を逆転させれば簡単に実現できる。
PerlにはCPANより Sort::Key::Top というモジュールが出ていて、n 個の要素を選択する関数群が提供されている。
ソートアルゴリズムの言語サポートの方が多いため、実際には単純にソートを行ってから選択する方法が(性能的には不利であるが)多く使われている。