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

ウィキペディア小見出し辞書

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 14:22 UTC 版)

「選択アルゴリズム」の記事における「パーティションベースの汎用選択アルゴリズム」の解説

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