選択アルゴリズム 言語サポート

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

言語サポート

リストの最大値と最小値を求める機能を持つ言語は多々あるが、汎用的な選択を組み込み機能で持っている言語はほとんどない。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.