乱数の順位付けのアルゴリズム

質問

[0,1]の範囲で乱数を1000個、配列に発生させて、小さいもの100個を選び出すアルゴリズムということを考えます（知りたいのは数値と配列番号、むしろ配列番号が大事）。まず想定できるのはソートですが、それにもいろんなものがあり、クイックソート、バブルソートなどが挙げられます。ソートのアルゴリズムは既に開発されつくしたのかもしれませんが、どのようになっているでしょうか。一番高速な（かつ間違いない）な方法が１つあればそれを採用したいのですが。
そして１つ厄介なのですが、そのトップ100個以外の900個はソートする必要がないということです。私が考えているアルゴリズムは、
１．既に100個の選ばれていると仮定（初期はすべて１）
２．新しい1個が来たとき、100個の最低値よりも小さいなら考慮の対象なのだから最低値を交換してその100個でソートする。そうでない場合は何もしない。
３．次の新しい1個を調べて、項目２をする。
４．発生させた1000個でそれを繰り返す。
このアルゴリズムだと100個のソートを何百回かぐらいやることになります。
これをするぐらいだったら1000個のソートを1回やればいいということになるでしょうか（不必要な残りの900個もソートされてしまう）。あるいはその1回の1000個のソートの中でやる必要のない処理を排除する工夫があるかもしれません。

問題が難しくなく、素人っぽくコード化できると思いますが、その分、非効率なところも放置されそうなので高速化できるコードの書き方があったら教えて頂きたいのですが。コードというよりアイディアだけ説明していただいても助かります。実際はフォートランになると思いますが。よろしくお願いします。

回答No.8

akayoroshi

クイックソートのアルゴリズムを使う。ピボットを任意に選んでそれ以下のものとそれより大きいものの2つのグループに分ける。ピボットに選んだ値が100番目よりも前にきたら、前半のグループと後半のグループをそれぞれ再帰的にソートする。100番目以降になっていたら、前半のグループだけを再帰的にソートする。これでできるのだが、ソートの途中でグループの大きさが100以下になっていたら挿入ソートを使うほうが速いかもしれない。