段階的ソートとしての選択
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 14:22 UTC 版)
「選択アルゴリズム」の記事における「段階的ソートとしての選択」の解説
不完全な選択ソートによる方法の利点は、前述したようにその後の選択にかかるコストを低減することにある。ある数列からどれだけ選択するか、その回数が事前に決まっていない場合がある。また、大きい方を選択するのか小さいほうを選択するのかも事前に決まっていない場合もある。このような場合、アルゴリズムを変形して、部分的なソートを行いながら選択をして、同時に将来の選択に備えることができる。 最小値ベースのアルゴリズムもパーティションベースのアルゴリズムも部分的なソートを行っている。最小値ベースのアルゴリズムでは指定されたインデックスまでのソートを行うので、特に小さいほうのインデックスを探す場合に効力を発揮する。パーティションベースのアルゴリズムは自動的に同様の振る舞いをすることはないが、ピボット値の選択を記憶しておけば、その後の選択を行う際にそれを利用して処理を効率化できる（特に最初のピボット値）。ピボット値を全て記憶しておけば、選択を行えば行うほどリストはソートされていく。ピボット値のリストを後でクイックソートで再利用することもできる。
※この「段階的ソートとしての選択」の解説は、「選択アルゴリズム」の解説の一部です。
「段階的ソートとしての選択」を含む「選択アルゴリズム」の記事については、「選択アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「段階的ソートとしての選択」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 段階的ソートとしての選択のページへのリンク
