選択アルゴリズム
不完全な選択ソートによる方法の利点は、前述したようにその後の選択にかかるコストを低減することにある。ある数列からどれだけ選択するか、その回数が事前に決まっていない場合がある。また、大きい方を選択するのか小さいほうを選択するのかも事前に決まっていない場合もある。このような場合、アルゴリズムを変形して、部分的なソートを行いながら選択をして、同時に将来の選択に備えることができる。
最小値ベースのアルゴリズムもパーティションベースのアルゴリズムも部分的なソートを行っている。最小値ベースのアルゴリズムでは指定されたインデックスまでのソートを行うので、特に小さいほうのインデックスを探す場合に効力を発揮する。パーティションベースのアルゴリズムは自動的に同様の振る舞いをすることはないが、ピボット値の選択を記憶しておけば、その後の選択を行う際にそれを利用して処理を効率化できる(特に最初のピボット値)。ピボット値を全て記憶しておけば、選択を行えば行うほどリストはソートされていく。ピボット値のリストを後でクイックソートで再利用することもできる。
ピボット値のインデックスと k を比較すればどちらに k 番目の値があるかが分かる。したがって、必要な方にだけ再帰的に処理を施せばよい。
クイックソートとの類似に注目されたい。前述の最小値ベースの選択アルゴリズムは不完全な選択ソートだったが、これは不完全なクイックソートであり、O(n) のパーティションのうち O(log n) の部分だけを処理する。この単純な手続きは線形時間の性能であることが期待でき、実際クイックソートのようによい性能を示す。これはin-placeアルゴリズムでもあり、一定のメモリ量しか使用しない。そのためには、以下のように末尾再帰をループにすればよい。
クイックソートと同様、このアルゴリズムはピボット値の選択によって性能が左右される。ピボット値として良くない値が一貫して選択された場合、その性能は前述の最小値ベースの選択と同等にまで低下する。