１～３００までの数字がランダムに並べられている配列があるとします。
その配列のうち最も大きい数値上位10個（この場合２９１～３００）を新しい配列に格納したいと思っています。
ちなみに最初のランダムな数値の配列はソートする必要は必ずしもないとします。
最も効率よく取得するにはどういう方法がよいでしょうか？
No.1
21
9
50pt
ぶっちゃけてしまうと、最初の配列を普通にソートして上位10個とるのがいちばん簡単で、しかも大抵は言うほどの大損にもなりません。なので、以下は O(n log n) 程度のソートが許容できない場合の話。
配列の内容について特に当てにできる性質が無いなら、クイックソートの再帰処理を端折って、普通ならpivotの上と下の両側について再帰するところを、必要な片側についてのみ続行するように変更するのが平均的に一番速いでしょう。
言語が指定されていないのでCっぽい擬似コードで。とりあえず入力値の配列 v[1]～v[300] を上書きする形で示しておきます。
18
18
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) のはず。
No.1
219
ここでベストアンサー
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) のはず。
回答ありがとうございます。
クイックソートを省略するわけですね！
これが平均的に速く動きそうですね。
試してみます。ありがとうございました。
No.2
797122
25pt
もっとも大きい数字をmで、新しい配列をb[]とすると
次のようなアルゴリズムになります。
for (i=0; i<10; i++) b[i]=m-i;
すいません。質問の説明が足りなかったみたいです。
No.3
4503437
25pt
こちらは参考になるでしょうか。
●C++編（標準ライブラリ） 第19章 ソートのアルゴリズム
○partial_sort()
partial_sort()は部分ソートを行います。このアルゴリズムは、例えば上位１０ 個の要素が正しくソートされてさえいれば、それより後ろの要素の並びはどうでもいい、というときに使えます。
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
rsc
2013/04/23 16:01:48
1
1
1
1
ghost
回答ありがとうございます。
2013/04/26 09:02:22クイックソートを省略するわけですね！
これが平均的に速く動きそうですね。
試してみます。ありがとうございました。