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

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

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

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

-------

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

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

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

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

No.14 回答者： -q7P2izb__ 回答日時： 2013/05/26 09:11

#10です。

ご返事が遅くなりまして申し訳ありません。

ご返答を一読した時に「！」と思いました。
確かに！-1000が最大値になる可能性もあるかも。
などなど。

まだまだアマチュアな自分でした。
それにしても、この本件の質問むずいっすね。

ありがとうございました。

No.13 回答者： Tacosan 回答日時： 2013/05/24 13:02

「同順位のデータが複数ある場合」については #4 で既に指摘されているものの, 質問者の反応がまったくないのでコンセンサスが取れていないところだと思います＞#12.

回答者にまともに対応する気, あるのかなぁ....

No.12 回答者： chie65535 回答日時： 2013/05/23 16:01

ANo.10の回答者さんへの回答。

＞最大値を-1000に書き換えていきます。
＞そして、n回目の最大値を探すときに、最大値を表示します。

「１番目に大きいのが３個ある」と、ｎが１、ｎが２、ｎが３の時に、全て同じ答えになっちゃいます。

要素数が１０個で、

20,1,20,2,20,3,4,5,6,7

と言うデータを想定してみましょう。

１番目に大きい値（最大値）は「20」、2番目は「7」、３番目は「６」の筈ですが、そうなりません。

また

-1000,-1001,-1000,-1002,-1003,-1004,-1001,-1002,-1000,-1000

と言うデータの場合も、正常に動きません。

１番目に大きい値（最大値）は「-1000」ですが、そうなりません。

No.11 回答者： chie65535 回答日時： 2013/05/23 15:48

「人間が手作業で調べる場合の行動」を、そのままプログラミングしましょう。

人間が手作業で調べる場合は、ソートなんて使いませんから。

人間が手作業で調べる場合の手順を、以下に書いてみる。

１．
白紙のメモとペンを用意し、メモに「１回目」とメモする。

２．
5,000,000個の中から、一番端にあるのを１個取って左手で持つ。

３．
次のを右手で取る。

４．
メモに「１回目」と書いてあったら、６．へ進む。

５．
メモに「今の最大値」が書いてあって、メモに書いてある「今の最大値」と、右手に持ったのを比べ、メモと等しいか大きいなら、それを無視して元に戻して、３．から繰り返す。

６．
両手の２つを比べて、大きいほうを左手に残し、小さいほうは戻す。

７．
３．から６．の手順を順番に最後までやって、最後に左手に１つ残す。

８．
メモに「今の最大値」が書いてあって、その「今の最大値」と、最後に左手に残ってたのを比べ、メモと等しいか大きいなら「ｎ番目に大きいのは無かった」と報告して作業終了。

９．
メモの「＊回目」の数と「ｎ」の数が一致したら、左手にあるのが「ｎ番目に大きいもの」になるので、それを答えにして作業終了。

１０．
メモの「＊回目」の数と「ｎ」の数が一致してないなら、メモの「＊回目」を書き直して１増やす。

１１．
「今の最大値」として、左手に持ってる物の数値をメモして、左手にあるのを戻して、２．からやり直す。メモの「今の最大値」は「消して書き直し」で構わない。

あとは、これを「C言語に置き換えるだけ」です。

No.10 回答者： -q7P2izb__ 回答日時： 2013/05/23 14:53

皆様のご意見を参考の上プログラム作成したものです。

私が本来の質問者様に代わって引き続き質問させて下さい。

■質問内容
私はCを長年独学していたものですが、
プログラムの書き方やアルゴリズムの立て方に自信がありません。
以下の内容をご覧になって頂いて指摘していただけると助かります。
どんな指摘でも構いませんので、よろしくお願い致します。

■仕様
最大値を１つずつ求めて、出る杭は打たれるように次々と
最大値を-1000に書き換えていきます。
そして、n回目の最大値を探すときに、最大値を表示します。


#define N 5000000;
int i ,j= 0; //変数
double maxValue = 0; //最大値の初期化
int temp = 0; //一時的な最大値を確保

if (n == 0) printf("不明"); //n=0の場合は不明
else if (n > 0) {
for (i = 0; i < n-1; i++) //上位n-1個分のデータの値を最低値にする
{
for (j = 0; j < N; j++) //すべてのデータから最大値を探す。
{
if (maxValue < data[j]) //最大値を求める
{
maxValue = data[j];
temp = j; //一時的な添字をtempに記憶させる
}
}
maxValue = 0; //最大値を初期化する(0に初期化)
data[temp] = -1000; //最大値のデータを最低値に変更する。
}
for (j = 0; j < N; j++) //今回の番で最大値を求める(n番目の最大値）
{
if (maxValue < data[j]) //最大値を求める
{
maxValue = data[j];
}
}
printf("maxValue_n = %f", maxValue); //n番目の最大値を表示（double型）
}

以上です。

No.9 回答者： m-take0220 回答日時： 2013/05/23 11:28

(1) 数値データから最大の数値を調べる関数を作る

(2) 数値データから指定された数値未満で最大の数値を調べる関数を作る

(1)と(2)はループだけでできるので、ソートする必要はない。
(1)で最大値を取得して、その最大値を指定して(2)を使えば2番目に大きい数値が得られる。
2番目に大きい数値を指定して(2)を使えば、3番目に大きい数値が得られる。
以下同様にすればn=0以外のn番目の数値が得られる。
n=0の時は、他の回答が指摘しているように仕様が不明。

No.8 回答者： Tacosan 回答日時： 2013/05/23 00:00

#1 が「ソートを使ってるからダメ」だったり #3 が「ヒープもアウト」とかいわれると, ここでいう「ソート」ってなんなんだ?

意識のすりあわせが必要だと思うので, ここでいう「ソート」とは何かを正確に書いてもらえませんか? 少なくとも, なぜ「ヒープもアウト」なのか理解できない (ヒープはただのデータ構造であってソートというアルゴリズムとは直接関係ない) ので.

あと, 「クイックセレクト」ってなんだろう.

No.7 回答者： jjon-com 回答日時： 2013/05/22 23:22

C言語を知らないのでJavaでコーディング。

import java.util.Random;

class Q8100119 {
static int M = 5000000;
static int N = 100;
static int[] array = new int[N];

public static void main(String[] args) {
Random rand = new Random();
for (int i = 0; i < N; i++) {
array[i] = rand.nextInt();
}
int minIdx = getMinIndex();
for (int i = N; i < M; i++) {
int k = rand.nextInt();
if (array[minIdx] < k) {
array[minIdx] = k;
minIdx = getMinIndex();
}
}
System.out.println("Answer: " + array[minIdx]);
}

static int getMinIndex() {
int minIdx = 0;
for (int i = 0; i < array.length; i++) {
if (array[minIdx] > array[i]) {
minIdx = i;
}
}
return minIdx;
}
}

No.6 回答者： yama1718 回答日時： 2013/05/22 23:11

単純です。

１．最小値(a)を調べる（端から端までサーチ）
２．次に大きい値(b)を調べる（端から端までサーチ）
　　1)二番目の値の候補(c)を読む
　　2)次に読んだ値が現在の最小値(a)よりも小さければスキップする
　　3)次に読んだ値が(a)よりも大きく(b)より小さければ新しい候補(b)とする
　　4)それを最後まで繰り返せば二番目の値(b)が確定しますね。
３．次の順位の値を調べる
　　(a)に(b)を入れて２．を繰り返す。
４．それをn回繰り返せばその時調べている最小値がn番目の値という事ですね。

ただし、同じ値が複数ある場合は同一順位の処理が必要なので、もう少し工夫が必要ですけどね。
これならソートもデータ以外の配列も使いません。
ただし、効率は悪いですけどね。

No.5 回答者： tatsu99 回答日時： 2013/05/22 20:35

考え方だけです。

データ数5000,000の配列のほかに
１．そのデータが使用済みかどうかを示すフラグだけの配列を5000,000個用意する。
ここでデータ[0]とフラグ[0]が対応する。
（データ[0]が有効ならフラグ[0]=1,無効ならフラグ[0]=0のように定義する）
同様にデータ[4999999]とフラグ[4999999]が対応する。
（データ[4999999]が有効ならフラグ[4999999]=1,無効ならフラグ[4999999]=0のように定義する）

２．このフラグ全体を１（有効）で初期化する。

３．　1番目に大きい数は、以下のようにして求める。
データの配列を順に検索し、最も大きい数値を求める。
このとき、その配列の何番目かも、記憶しておき（X番目とすると）、
そのフラグ［X］を無効にする。
４．　2番目に大きい数は、以下のようにして求める。
データの配列を順に検索し、最も大きい数値を求める。
但し、フラグが無効のデータはスキップする。
このとき、その配列の何番目かも、記憶しておき（X番目とすると）、
そのフラグ［X］を無効にする。
５．同様にしてｎ番目に大きい数値を求める。
-------------------------
この方式で、同じ値が存在する場合は、その値が、異なる順番に使われます。
データの値が１０のものが２つあり、以外は全て０なら、
1番目は１０
2番目は１０
３番目は０
４番目は０
になります。
--------------------------
又、入っているデータがint型でなおかつ、０以上の値であるという条件なら
フラグの配列を作る必要はありません。
データに-1を設定し、データが-1なら無効データとすればよいです。
-------------------------
不明点があれば、補足してください。