選択アルゴリズム

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

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

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

  **function** minimum(a[1..n])
      minIndex := 1
      minValue := 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] 2) であり、*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 2 より大きくなった場合に、効率を改善するために再構成（つまり *h* を大きくする）する必要がある。この方式はデータ数が分かっている場合の順序統計量を探すのに適している（例えば学生の成績の統計処理など）。各格納場所の値の範囲を 1 としてそれぞれに要素数をカウントするようにするのが最も優れている。そのようなハッシュテーブルは要約統計量でデータを分類するための度数分布表に似ている。

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

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

この下限は *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(*n*log *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&ndash;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&ndash;196. Section 14.1: Dynamic order statistics, pp.302&ndash;308.