選択アルゴリズム

選択アルゴリズム（英: selection algorithm）とは、数列から k 番目に小さい（あるいは k 番目に大きい）数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、k 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。k 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。

ソートを伴う選択

単純でよく使われるアルゴリズムは、数列にソートを施してから k 番目の要素を抜き出す方法である。これはある問題から別の問題への還元の例である。これはひとつの数列からいくつもの選択を行いたい場合に便利であり、最初の1回だけソートをすれば、ソート済みの数列からの選択は非常に簡単になる。選択を1回しかしない場合や選択のたびに数列の内容が大幅に変更される場合、この方法は高くつき、一般に最低でも O(n log n) の時間を要する。ここで n はリストの長さである。

線形最大・最小アルゴリズム

最悪でも線形時間となる最小値・最大値を求めるアルゴリズムは自明である。2つの変数を使い、一方にはそれまでの最大値/最小値のリスト上のインデックスを格納し、もう一方にその値そのものを格納する。リストを順次見ていき、それらしい値を見つけたら変数を更新する。

 function minimum(a[1..n])
     minIndex := 1
     minValue := a[1]
     for i from 2 to n
         if a[i] < minValue
             minIndex := i
             minValue := a[i]
     return minValue

 function maximum(a[1..n])
     maxIndex := 1
     maxValue := a[1]
     for i from 2 to n
         if a[i] > maxValue
             maxIndex := i
             maxValue := a[i]
     return maxValue

このアルゴリズムは、全順序集合の有限部分集合 A（例えば、整数、実数、辞書の単語群などの部分集合）について、A に含まれない要素 x があるとき、 $\operatorname {\max } (A\cup \{x\})=\operatorname {\max } (\{\operatorname {\max } A,x\})$ が成り立つという定理に基づいている。このとき最小値や最大値が複数個存在する可能性に注意が必要である。上記擬似コードの比較は厳密であるため、このアルゴリズムでは最小のインデックスの最小値を探し出す。厳密でない比較（≤ および ≥）を用いれば、最大のインデックスの最小値を探し出すことになる。

最大値と最小値を同時に求めたい場合、若干の改善方法としてペア単位の比較が考えられる。つまり、奇数番目と偶数番目の要素を比較し、大きい方を最大値と、小さいほうを最小値と比較するのである。別の手法として分割統治法がある。つまり、リストを半分に分け、前半と後半それぞれの最大値・最小値を求め、それらの値から全体の最大値・最小値を求める。

非線形選択アルゴリズム

最大値/最小値アルゴリズムをそのまま使って、k 番目に小さい値（または k番目に大きい値）を求めるアルゴリズムは簡単に作成できるが、効率は不十分である。必要な時間は O(kn) で、k が小さければ小さいほど効率が良い。このアルゴリズムでは、単に最もそれらしい値を見つけてそれをリストの先頭に移動させ、必要な k番目に達するまでそれを繰り返す。それはちょうど不完全な選択ソートと同じである。以下に小さい値を探すアルゴリズムを示す。

 function select(a[1..n], k)
     for i from 1 to k
         minIndex = i
         minValue = a[i]
         for j from i+1 to n
             if a[j] < minValue
                 minIndex = j
                 minValue = a[j]
         swap a[i] and a[minIndex]
     return a[k]

この方式には以下の利点がある。

j 番目に小さい値がわかっている状態では、k 番目に小さい値を求めるのにかかる時間は O(j + (k-j)²) であり、k ≤ j なら O(k) となる。
線形リストデータ構造を使うことができる。一方、後述するパーティションベースの手法ではランダムアクセスを必要とする。

パーティションベースの汎用選択アルゴリズム

k 番目に大きい値を選択するための最悪でも線形時間のアルゴリズムは、少なくとも1つ存在している。これは、マヌエル・ブラム、ロバート・フロイド、Pratt、ロバート・タージャンが1973年の論文 Time bounds for selection で発表したものである。そのアルゴリズムは独自の発明部分とクイックソートで使われている技法を合わせている。

クイックソートでは、リストをある値より小さい数のリストとそれより大きい数のリストに分割するパーティションと呼ばれるサブプロシージャがあり、これは線形時間である。a[pivotIndex] という値でパーティションを行う擬似コードを以下に示す。

 function partition(a, left, right, pivotIndex)
     pivotValue := a[pivotIndex]
     swap a[pivotIndex] and a[right]  // ピボット値を最後に置く
     storeIndex := left
     for i from left to right-1
         if a[i] ≤ pivotValue
             swap a[storeIndex] and a[i]
             storeIndex := storeIndex + 1
     swap a[right] and a[storeIndex]  // ピボット値を最終的な場所に置く
     return storeIndex

クイックソートでは、2つに分けたリストをそれぞれ再帰的にソートしていき、最善で Ω(n log n) の時間がかかる。しかし、選択ではどちらのパーティションに必要な値があるか分かっている。ピボット値のインデックスと k を比較すればどちらに k 番目の値があるかが分かる。したがって、必要な方にだけ再帰的に処理を施せばよい。

 function select(a, k, left, right)
     select a pivot value a[pivotIndex]
     pivotNewIndex := partition(a, left, right, pivotIndex)
     if k = pivotNewIndex
         return a[k]
     else if k < pivotNewIndex
         return select(a, k, left, pivotNewIndex-1)
     else
         return select(a, k-pivotNewIndex, pivotNewIndex+1, right)

クイックソートとの類似に注目されたい。前述の最小値ベースの選択アルゴリズムは不完全な選択ソートだったが、これは不完全なクイックソートであり、O(n) のパーティションのうち O(log n) の部分だけを処理する。この単純な手続きは線形時間の性能であることが期待でき、実際クイックソートのようによい性能を示す。これはin-placeアルゴリズムでもあり、一定のメモリ量しか使用しない。そのためには、以下のように末尾再帰をループにすればよい。

 function select(a, k, left, right)
     loop
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         if k = pivotNewIndex
             return a[k]
         else if k < pivotNewIndex
             right := pivotNewIndex-1
         else
             left := pivotNewIndex+1

クイックソートと同様、このアルゴリズムはピボット値の選択によって性能が左右される。ピボット値として良くない値が一貫して選択された場合、その性能は前述の最小値ベースの選択と同等にまで低下する。

「中央値の中央値」を用いたクイックセレクト

→詳細は「中央値の中央値」を参照

一貫して良いピボット値を見つけることができれば、クイックセレクトを最悪でも線形時間にすることができる。そのためにまず、元の配列を5つずつの要素の小配列に分割する。次にその小配列ごとに中央値を探し、その各中央値だけを抽出した配列に対して、さらに選択アルゴリズムを再帰的に適用する。そうして見つかった中央値の中央値は、ピボット値として最適であり、1回の反復で元の配列の要素数より一定の割合（最善で3割、最悪でも7割）に減らすことができる。

ただし、この方法では最悪時間は確かに線形になるが、平均時間は、実際にはピボット値を無作為に選ぶなどの素朴な方式の方が優れている。

段階的ソートとしての選択

不完全な選択ソートによる方法の利点は、前述したようにその後の選択にかかるコストを低減することにある。ある数列からどれだけ選択するか、その回数が事前に決まっていない場合がある。また、大きい方を選択するのか小さいほうを選択するのかも事前に決まっていない場合もある。このような場合、アルゴリズムを変形して、部分的なソートを行いながら選択をして、同時に将来の選択に備えることができる。

最小値ベースのアルゴリズムもパーティションベースのアルゴリズムも部分的なソートを行っている。最小値ベースのアルゴリズムでは指定されたインデックスまでのソートを行うので、特に小さいほうのインデックスを探す場合に効力を発揮する。パーティションベースのアルゴリズムは自動的に同様の振る舞いをすることはないが、ピボット値の選択を記憶しておけば、その後の選択を行う際にそれを利用して処理を効率化できる（特に最初のピボット値）。ピボット値を全て記憶しておけば、選択を行えば行うほどリストはソートされていく。ピボット値のリストを後でクイックソートで再利用することもできる。

準線形時間での選択のためのデータ構造使用

整列されていないデータのリストがあるとき、最小値を求めるには全要素を調べる必要があるため（さもなくば最小値を見逃す可能性がある）、線形時間 (Ω(n)) を必要とする。リストを作成する際に全データが常に整列するようにすれば、k 番目に大きい値の選択も簡単になる。しかし、そのためにはリストの途中へのデータの挿入に線形時間を必要とする（2つのリストのマージと同様である）。

準線形時間で順序統計量を求める戦略は、データを選択を行うのに適したデータ構造に格納するものである。そのようなデータ構造として木構造ベースのものと度数分布表がある。

最小値（または最大値）だけが必要な場合、優先度付きキューが適している。これは最小値（または最大値）を一定時間で探すことができ、他の挿入などの操作も O(log n) かそれよりよい性能を示す。より一般的には平衡2分探索木を使えば、要素の挿入も k 番目に大きい値の選択も O(log n) の時間で可能である。各ノードには配下に何個のノードがあるかをカウントした値を格納しておき、どのパスを辿るかを決定するのに使用する。この情報はノード（つまり新たなデータ）を追加したとき、接続される上位ノード群だけを修正すればよいので O(log n) の時間で済む。また、木の回転はそれに関わるノード群だけに影響する。

別の単純な戦略として、ハッシュテーブルのようなコンセプトに基づくものがある。データが取りうる値の範囲が予め分かっている場合、それを h 個の部分に分け、h 個の格納場所を設定する。要素を新たに挿入する際、その値が含まれる範囲に対応する格納場所にそれを置く。最大値や最小値を探すには、空でない格納場所を大きいほうからか小さいほうから探していき、その格納場所の中で最大値や最小値を探せばよい。一般に k 番目の要素を探すには、各格納場所に入れた要素数をカウントしておき、端からその値を加算していって k 番目を含む格納場所を探す。そして、その格納場所内の要素群から必要な要素を線形時間アルゴリズムで探し出せばよい。

h のサイズをおよそ sqrt(n) としたとき、データの分布がほぼ一様であれば、この方式による選択は O(sqrt(n)) の時間になる。しかし、データが狭い範囲に固まって出現すると（クラスタリング）、この手法では1つの格納場所に多大な要素が格納されることになってしまう（クラスタリングはハッシュ関数をうまく設定することで排除できるが、k 番目に大きい値をばらばらにハッシュされた中から探すのは現実的でない）。さらにハッシュテーブルと同様で、この方式では要素数 n が増大して h² より大きくなった場合に、効率を改善するために再構成（つまり h を大きくする）する必要がある。この方式はデータ数が分かっている場合の順序統計量を探すのに適している（例えば学生の成績の統計処理など）。各格納場所の値の範囲を 1 としてそれぞれに要素数をカウントするようにするのが最も優れている。そのようなハッシュテーブルは要約統計量でデータを分類するための度数分布表に似ている。

k個の最小・最大要素の選択

別の基本的な選択問題として、k 個の最大要素（または最小要素）を選択する問題がある。例えば、売り上げトップ100社のようなリストを得たい場合に相当する。単純だが効率的でない手法はいくつか存在する。上述の選択アルゴリズムで1個ずつ要素を選択していけば O(kn) の時間で k 個の要素を選択できる。これは、k 番目までの選択ソートを実施するのと同じである。もし log n が k よりずっと小さいなら、リスト全体をソートしてしまう方が効率的である。

別の単純な方法は、ヒープや平衡2分探索木のような順序を維持できるデータ構造にデータを格納することである。データ構造に k 個以上の要素があるなら、いらない要素を削除する（小さい方の要素群が必要なら最大の要素を削除する）。これには O(log k) の時間がかかる。要素の挿入にも同じ時間がかかり、全体として O(nlog k) の時間を要する。

これらよりも効率的な手法として、マージソートやクイックソートに基づいた部分ソートアルゴリズムがある。クイックソート方式の方が簡単で、選択したい k 個の要素群（の一部）を含まないパーティションをソートしない。ピボット値が k 番目かそれ以降なら、左側のパーティションだけに再帰を施せばよい。

 function quicksortFirstK(a, left, right, k)
     if right > left
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         quicksortFirstK(a, left, pivotNewIndex-1, k)
         if pivotNewIndex < k
             quicksortFirstK(a, pivotNewIndex+1, right, k)

このアルゴリズムにかかる時間は O(n + klogk) であり、実際非常に効率が良い。特に、n に比較して k が十分小さいなら、選択ソートを使うようにすれば効率が向上する。

選択する k 個の要素がソートされている必要がないなら、もっと効率化することができる。その場合、k 番目の要素を含むパーティションだけに再帰を施せばよく、その前後はソートする必要がない。

 function findFirstK(a, left, right, k)
     if right > left
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         if pivotNewIndex > k  // new condition
             findFirstK(a, left, pivotNewIndex-1, k)
         if pivotNewIndex < k
             findFirstK(a, pivotNewIndex+1, right, k)

このアルゴリズムに掛かる時間は O(n) であり、アルゴリズムとしては最善の部類になる。

別の方法はトーナメントアルゴリズムである。まず、隣接するペアで試合（比較）を行い、勝者を次の試合に進めていき、最終的に優勝を決定する。このときトーナメント木を生成する。この時点で 2位の要素は優勝者に直接負けた要素であるはずなので、木構造を辿っていけば O(log n) の時間で探すことができる。このとき新たなトーナメント木を生成する。3位の要素は 2位の要素に直接負けた要素のはずなので、2つのトーナメント木からそれを探し出す。このようにして k 個の要素を探し出すまで処理を行う。このアルゴリズムは O(n + k log n) の時間がかかる。

k = 2 の場合、O(n + log n) の時間で選択ができる。

下限

ドナルド・クヌースは、The Art of Computer Programming の中で、k 番目に小さい要素を n 個の要素から（比較だけで）選択するのに必要な比較回数の下限を論じている。最大値または最小値を求めるのに必要な比較回数の下限は n − 1 である。これを求めるために各試合で1回の比較を行うトーナメントを想定する。トーナメント優勝者以外の選手は優勝者が決定するまでに必ず1回負けているので、比較回数の下限が n − 1 となるのである。

1番目以外では話はやや複雑になる。k 番目に小さい値を求めるには少なくとも以下の回数の比較が必要である。

n-k+\sum _{n+1-k<j\leq n}\lceil {\log _{2}j}\rceil

この下限は k=2 のとき成り立つが、さらに大きな 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 個の要素を選択する関数群が提供されている。

ソートアルゴリズムの言語サポートの方が多いため、実際には単純にソートを行ってから選択する方法が（性能的には不利であるが）多く使われている。

参考文献

M. Blum, R.W. Floyd, V. Pratt, R. Rivest and R. Tarjan, "Time bounds for selection," J. Cornput. System Sci. 7 (1973) 448-461.
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207–219.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp.183–196. Section 14.1: Dynamic order statistics, pp.302–308.