この問題に関する情報は、選択アルゴリズムで見つけることができます。
前述のように、あなたが言及しているのは選択アルゴリズムです。具体的には、クイックソートへの言及は、パーティション ベースの選択を考えていることを示唆しています。
仕組みは次のとおりです。
- クイックソートの場合と同様に、リストの半分近くにあると思われるピボットを選択することから始めます。次に、アイテムのリスト全体を調べて、ピボットよりも小さいすべてのアイテムがリストの先頭にあり、ピボットよりも大きいすべてのアイテムが最後になるまで、物事を交換します。ピボットは真ん中の残りのスポットに入ります。
- 通常、クイックソートではピボットの両側で再帰しますが、選択アルゴリズムでは、関心のあるインデックスを含む側でのみ再帰します。インデックス 2 (インデックス 0 が 1 番目に低い値であるため)。
- リージョンを 1 つのインデックスだけに絞り込むと、再帰を停止できます。最後に、「m-1」個の最小オブジェクトのソートされていないリストと、「n-m」個の最大オブジェクトのソートされていないリストがもう 1 つあります。 「m」番目のオブジェクトは中間になります。
このアルゴリズムは、最大の m 要素のソートされたリストを見つけるのにも適しています... m 番目に大きい要素を選択し、その上のリストをソートするだけです。または、少し高速なアルゴリズムの場合、クイックソート アルゴリズムを実行しますが、ソートされた値を見つけたい領域と重ならない領域への再帰は拒否します。
これの本当に素晴らしい点は、通常 O(n) 時間で実行されることです。最初は、リスト全体が表示されます。最初の再帰では、約半分、次に 4 分の 1 などを確認します。したがって、約 2n 要素を確認するため、O(n) 時間で実行されます。残念ながら、クイックソートのように、一貫して悪いピボットを選択すると、O(n 2 で実行されます。 ) 時間。