「中央値の中央値」を用いたクイックセレクト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 14:22 UTC 版)
「選択アルゴリズム」の記事における「「中央値の中央値」を用いたクイックセレクト」の解説
詳細は「中央値の中央値」を参照 一貫して良いピボット値を見つけることができれば、クイックセレクトを最悪でも線形時間にすることができる。そのためにまず、元の配列を5つずつの要素の小配列に分割する。次にその小配列ごとに中央値を探し、その各中央値だけを抽出した配列に対して、さらに選択アルゴリズムを再帰的に適用する。そうして見つかった中央値の中央値は、ピボット値として最適であり、1回の反復で元の配列の要素数より一定の割合（最善で3割、最悪でも7割）に減らすことができる。 ただし、この方法では最悪時間は確かに線形になるが、平均時間は、実際にはピボット値を無作為に選ぶなどの素朴な方式の方が優れている。
※この「「中央値の中央値」を用いたクイックセレクト」の解説は、「選択アルゴリズム」の解説の一部です。
「「中央値の中央値」を用いたクイックセレクト」を含む「選択アルゴリズム」の記事については、「選択アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「「中央値の中央値」を用いたクイックセレクト」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 「中央値の中央値」を用いたクイックセレクトのページへのリンク
