クイックセレクト
クイックセレクト(英: quickselect)は配列内の k 番目に小さい要素を見つけるための選択アルゴリズム。クイックソートによく似たアルゴリズムで、クイックソートと同じくアントニー・ホーアに発見されたため、 ホーアの選択アルゴリズムとも呼ばれる。 クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。
クイックセレクトは、クイックソートと同じように1つの要素をピボットとして選択し、ピボットに基づいてデータをピボットよりも小さいかに大きいか二分割するのを繰り返す。ただし、クイックソートのように分割した両方の区間に対して再帰するのではなく、クイックセレクトは一方の側、つまり検索している要素のある側にのみ再帰する。これにより、平均計算量が軽減される。平均計算量はクイックソートが Θ ( n log  n ) {\displaystyle \Theta (n\log n)} なのに対してクイックセレクトは Θ ( n ) {\displaystyle \Theta (n)} 。最悪計算量はクイックソートと同じく O ( n 2 ) {\displaystyle O(n^{2})} 。
クイックソートと同様に、クイックセレクトは通常、In-placeアルゴリズムとして実装され、 k 番目の要素を選択するだけでなく、データを部分的にソートする。ソートとの関係の詳細については、選択アルゴリズムを参照。