アルゴリズムに関する質問です。

1~300までの数字がランダムに並べられている配列があるとします。
その配列のうち最も大きい数値上位10個(この場合291~300)を新しい配列に格納したいと思っています。
ちなみに最初のランダムな数値の配列はソートする必要は必ずしもないとします。
最も効率よく取得するにはどういう方法がよいでしょうか?

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2013/04/23 01:47:03
  • 終了:2013/04/26 09:13:04

ベストアンサー

id:vow No.1

ghost回答回数21ベストアンサー獲得回数92013/04/23 09:13:11

ポイント50pt

ぶっちゃけてしまうと、最初の配列を普通にソートして上位10個とるのがいちばん簡単で、しかも大抵は言うほどの大損にもなりません。なので、以下は O(n log n) 程度のソートが許容できない場合の話。

配列の内容について特に当てにできる性質が無いなら、クイックソートの再帰処理を端折って、普通ならpivotの上と下の両側について再帰するところを、必要な片側についてのみ続行するように変更するのが平均的に一番速いでしょう。

言語が指定されていないのでCっぽい擬似コードで。とりあえず入力値の配列 v[1]~v[300] を上書きする形で示しておきます。

l=1, r=300, t=10;
while (l < r) {
	k = v[t], p = l, q = r;		// 仮の順位tを基準に切り分ける
	while (1) {
		while (v[p] > k) ++p;		//小さい順にとるなら <
		while (k > v[q]) --q;		//小さい順にとるなら <
		if (p > q) break;
		s = v[p], v[p] = v[q], v[q] = s;	//入れ替え
		++p, --q;
	}
	if (q < t) l = p;		//仮の順位tより後が多すぎた場合
	if (t < p) r = q;		//仮の順位tより前が多すぎた場合
}

これで v[t] が順位tになり、かつ v[1..t] >= v[t] >= v[t..300] が保証されるので、v[1..t] がそのまま上位t個(順不同)になります。これで O(n) のはず。

id:jinchangz

回答ありがとうございます。
クイックソートを省略するわけですね!
これが平均的に速く動きそうですね。
試してみます。ありがとうございました。

2013/04/26 09:02:22

その他の回答(2件)

id:vow No.1

ghost回答回数21ベストアンサー獲得回数92013/04/23 09:13:11ここでベストアンサー

ポイント50pt

ぶっちゃけてしまうと、最初の配列を普通にソートして上位10個とるのがいちばん簡単で、しかも大抵は言うほどの大損にもなりません。なので、以下は O(n log n) 程度のソートが許容できない場合の話。

配列の内容について特に当てにできる性質が無いなら、クイックソートの再帰処理を端折って、普通ならpivotの上と下の両側について再帰するところを、必要な片側についてのみ続行するように変更するのが平均的に一番速いでしょう。

言語が指定されていないのでCっぽい擬似コードで。とりあえず入力値の配列 v[1]~v[300] を上書きする形で示しておきます。

l=1, r=300, t=10;
while (l < r) {
	k = v[t], p = l, q = r;		// 仮の順位tを基準に切り分ける
	while (1) {
		while (v[p] > k) ++p;		//小さい順にとるなら <
		while (k > v[q]) --q;		//小さい順にとるなら <
		if (p > q) break;
		s = v[p], v[p] = v[q], v[q] = s;	//入れ替え
		++p, --q;
	}
	if (q < t) l = p;		//仮の順位tより後が多すぎた場合
	if (t < p) r = q;		//仮の順位tより前が多すぎた場合
}

これで v[t] が順位tになり、かつ v[1..t] >= v[t] >= v[t..300] が保証されるので、v[1..t] がそのまま上位t個(順不同)になります。これで O(n) のはず。

id:jinchangz

回答ありがとうございます。
クイックソートを省略するわけですね!
これが平均的に速く動きそうですね。
試してみます。ありがとうございました。

2013/04/26 09:02:22
id:dawakaki No.2

だわかき回答回数797ベストアンサー獲得回数1222013/04/23 17:30:25

ポイント25pt

もっとも大きい数字をmで、新しい配列をb[]とすると
次のようなアルゴリズムになります。

for (i=0; i<10; i++)    b[i]=m-i;
id:jinchangz

すいません。質問の説明が足りなかったみたいです。

2013/04/26 09:11:37
id:rsc96074 No.3

rsc回答回数4385ベストアンサー獲得回数4002013/04/26 06:14:12

ポイント25pt

 こちらは参考になるでしょうか。
●C++編(標準ライブラリ) 第19章 ソートのアルゴリズム

○partial_sort()
partial_sort()は部分ソートを行います。このアルゴリズムは、例えば上位10 個の要素が正しくソートされてさえいれば、それより後ろの要素の並びはどうでもいい、というときに使えます。

http://www.geocities.jp/ky_webid/cpp/library/019.html
●開発メモ: トップNソートの検討 - FAL Labs
http://fallabs.com/blog-ja/promenade.cgi?id=104
●heap sortを使った上位ランキング取得プログラム - 遙かへのスピード ...
http://d.hatena.ne.jp/thorikawa/20091221/p1

  • id:rsc96074
     上位10個が分かっているのでそのまま入れるという、意地悪クイズじゃないでしょうね。(^_^;
    for(i=0; i< 10; i++) b[i]=i+291;
  • id:vow
    まあ実際の状況を簡略化して日本語にする間にバグっただけじゃないですかねぇ。
    (この場合291~300)を真に受けたら「算法に関する質問」に価しませんよ:-)

    ちなみに値の範囲が1~300であることが本当に実際の条件であるなら、分布数え(distribution counting)も有力な候補になります。これも O(n)。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません