クイックセレクト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/03 06:32 UTC 版)
クイックセレクト（英: quickselect）は配列内の k 番目に小さい要素を見つけるための選択アルゴリズム。クイックソートによく似たアルゴリズムで、クイックソートと同じくアントニー・ホーアに発見されたため、 ホーアの選択アルゴリズムとも呼ばれる。 [1]クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。
- ^ Hoare, C. A. R. (1961). “Algorithm 65: Find”. Comm. ACM 4 (7): 321–322. doi:10.1145/366622.366647.
- ^ Alexandrescu, Andrei (2020年5月14日). “Lomuto's comeback”. dlang.org. 2022年3月23日閲覧。
- ^ Blum-style analysis of Quickselect, David Eppstein, October 9, 2007.
[続きの解説]
「クイックセレクト」の続きの解説一覧
- 1 クイックセレクトとは
- 2 クイックセレクトの概要
- 3 派生
- 4 関連項目
- クイックセレクトのページへのリンク
