選択アルゴリズム

選択アルゴリズムとは

選択アルゴリズムは、与えられた数列の中から、k番目に小さい（または大きい）要素を特定するためのアルゴリズムです。これは、最小値、最大値、中央値を求めるアルゴリズムの一般化と見なすことができ、順序統計量とも呼ばれます。

基本的な考え方

最も単純なアプローチは、数列全体をソートしてからk番目の要素を取り出す方法ですが、これは計算量が増大するため、効率的とは言えません。より高度なアルゴリズムでは、ソートせずにk番目の要素を直接見つけ出すことを目指します。

線形時間アルゴリズム

平均して線形時間（O(n)）で動作する選択アルゴリズムが存在します。例えば、最小値や最大値を求めるアルゴリズムは、リストを一度走査するだけで実現できます。また、最悪の場合でも線形時間で動作するアルゴリズムも知られています。

アルゴリズムの種類

選択アルゴリズムには、以下のような種類があります。

ソートに基づく選択: 数列をソートしてからk番目の要素を取り出す方法。単純だが効率が悪い。
線形時間最大・最小アルゴリズム: リストを一度走査して最小値または最大値を求める。効率的。
非線形選択アルゴリズム: 最大値/最小値アルゴリズムを拡張してk番目の要素を求める。
パーティションベースの汎用選択アルゴリズム: クイックソートの分割統治法を応用し、k番目の要素を効率的に見つける。
中央値の中央値を用いたクイックセレクト: ピボットの選択を最適化することで、最悪でも線形時間で動作する。
段階的ソートとしての選択: 部分的なソートを行いながら選択を進め、将来の選択に備える。
* データ構造を用いた準線形時間の選択: 木構造や度数分布表などのデータ構造を活用し、効率的に選択を行う。

各アルゴリズムの詳細

ソートを伴う選択

最も直感的な方法は、数列をソートしてからk番目の要素を抽出することです。しかし、ソート処理には最低でもO(n log n)の計算時間が必要となるため、選択を1回だけ行う場合や、数列の内容が頻繁に変更される場合には不向きです。

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

最小値や最大値を求めるアルゴリズムは、リストを一度走査するだけで実現できます。具体的には、現在の最小値（または最大値）を保持する変数を用意し、リストの要素と比較しながら更新していくことで、最終的な最小値（または最大値）を得ます。


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

非線形選択アルゴリズム

最小値/最大値アルゴリズムを拡張して、k番目に小さい値を見つけることもできます。リストをk回走査し、その都度最小値を見つけてリストの先頭に移動させることで、k番目の要素を特定します。ただし、このアルゴリズムの計算量はO(kn)であり、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]

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

このアルゴリズムは、クイックソートで使用されるパーティション操作を応用しています。まず、リストをピボット値に基づいて2つのパーティションに分割し、k番目の要素がどちらのパーティションに含まれるかを判断します。必要なパーティションに対してのみ再帰的に処理を行うことで、効率的に選択を行います。計算量の期待値は線形時間であり、実際の性能も優れています。


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

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^2)にまで悪化する可能性があります。そこで、ピボット値として、数列の中央値に近い値（中央値の中央値）を選択することで、計算量を線形時間に抑えることができます。ただし、この方法では、平均的な性能はランダムにピボットを選ぶよりも劣ることが知られています。

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

この手法では、部分的なソートを行いながら選択を進めます。これにより、将来的に別の要素を選択する場合に、計算量を削減することが期待できます。最小値ベースのアルゴリズムやパーティションベースのアルゴリズムを応用することで、段階的なソートと選択を同時に実現します。

データ構造を用いた準線形時間の選択

木構造や度数分布表といったデータ構造を使用することで、準線形時間で要素の選択を行うことができます。例えば、平衡2分探索木を使用すれば、要素の挿入もk番目の要素の選択も、O(log n)の時間で行うことができます。

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

k個の最小（または最大）要素を選択する場合、選択アルゴリズムをk回繰り返す方法や、ヒープなどのデータ構造を利用する方法などがあります。クイックソートに基づいた部分ソートアルゴリズムも有効です。

計算量の下限

選択アルゴリズムには、計算量の理論的な下限が存在します。例えば、最小値や最大値を求めるのに必要な比較回数の下限はn-1回です。より一般的に、k番目に小さい要素を選択する場合、最低でも一定回数の比較が必要であることが知られています。

言語サポート

多くのプログラミング言語で、最大値や最小値を求める機能は提供されていますが、汎用的な選択アルゴリズムは組み込み機能として提供されていないことが多いです。C++では、nth_elementというテンプレートが提供されており、線形時間での選択が可能です。

まとめ

選択アルゴリズムは、データ列から特定の順位の要素を効率的に見つけ出すための重要なアルゴリズムです。様々なアルゴリズムが存在しますが、問題の特徴に応じて適切なものを選択することが重要です。計算量の下限を理解することで、アルゴリズムの効率を評価することができます。

もう一度検索