ｎ番目に大きい数を求めるアルゴリズム（Ｃ言語）

研修の課題で以下のような課題がだされています。

-------
データ数5000,000の数値データ（順序はランダム）の中で、n番目に大きい数を求めなさい。
nは、0～100とする。

但し、ソートは一切使ってはいけない。

-------

ソートを使ってはいけないという縛りが…大変、厳しく・・・
クイックセレクト等、どれも必ずソートを要するものしか思いつかないのです。。。

下位ｎ個の数値を保持する方法→（ソート要）
クイックセレクト→（ソート要）

他に何か、ソートを使わない解法はあるのでしょうか。

アイディアをください。
よろしくお願いします。

No.4 回答者： ky072 回答日時： 2013/05/22 19:54

No.3 の方もおっしゃっていますが、

まず、n=0については出題者に確認した方が良いでしょう。

それから「入力に同じ値が複数存在する可能性があるか」や、
同じ値が複数存在した場合の「n番目に大きい数」の定義も
確認した方がいいでしょう。
例えば 100, 100, 90, 90, 80, 50 というデータが許容されるか、
許容された場合に「3番目に大きい数」は 90 なのか 80 なのか。
これによって少し実装が変わるはずです。


回答ですが、No.1 の方もおっしゃっているように、
「上位n個の数値を保持する方法」をベースにできます。
「下位n個」とありますが、「上位n個」ですよね？
それを前提に話を進めます。

上位n個の配列を維持するのに、
ソートは絶対に必要ではありません。
n個全てを並び替えてしまうとソートになりますが、
実際に必要なのは配列内のn個の要素の中で、
最小の要素がどれであるかを知ることだけです。

配列内のn個のそれぞれの要素について、
他の全要素と比較し、
それが最小の要素であるかをチェックしてマークします。
最小がどれであるかを知るだけで、並び替えはしません。

入力に対しての処理はこうなります。
入力が配列内の最小の要素よりも大きい場合には、
最小の要素と入れ替えます。
そしてまた最小の要素を見つけなおします。

こうして最後のデータまで処理を終えれば、
配列内の最小の要素＝「n番目に大きい数」になります。

つまり、配列には出現した順にデータを詰めていき、
どの要素が最小値であるかをマークするだけにすることで、
ソートを回避するわけです。
配列内の最小値よりも小さいデータは捨て、
最小値よりも大きいデータが来たら入れ替えるのです。
結果、配列内の順序はぐちゃぐちゃなままで、
「n番目に大きい数」が求められることになります。

No.3 回答者： Tacosan 回答日時： 2013/05/22 18:49

「ソートは一切使ってはいけない」という制約がどこまで厳しいのかによりそうだけど, 例えばヒープを作るとか.

ところで, n に 0 を与えた場合は何を答えればいいんだろう.

この回答への補足

問題の制約で、n >= 1　という条件が付いています。
また、ソートは一切使ってはいけない…という通り、本当に一切使ってはいけないのです。

ヒープもアウトなんだそうです。

何かありませんでしょうか。。。

補足日時：2013/05/22 19:28

No.2 回答者： papapa0427 回答日時： 2013/05/22 18:42

ヒントだけ

for文と配列を使う。

No.1 回答者： kmee 回答日時： 2013/05/22 18:40

> 下位ｎ個の数値を保持する方法→（ソート要）

これでできますよ。
ちょっと考えてみたらどうでしょう。

この回答への補足

> 下位ｎ個の数値を保持する方法→（ソート要）


これが、
「一切ソートを使ってはいけない」
という条件によりアウトになります。

下位ｎ個の数値を保持する辞典でｎ個の中のソートをするのでアウトなんだそうです。

補足日時：2013/05/22 19:29