▽1
●
ghost ●50ポイント ベストアンサー |
ぶっちゃけてしまうと、最初の配列を普通にソートして上位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) のはず。
もっとも大きい数字をmで、新しい配列をb[]とすると
次のようなアルゴリズムになります。
for (i=0; i<10; i++) b[i]=m-i;
こちらは参考になるでしょうか。
●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