人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

●質問者: jinchangz
●カテゴリ:コンピュータ 学習・教育
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

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) のはず。


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

2 ● だわかき
●25ポイント

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

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

jinchangzさんのコメント
すいません。質問の説明が足りなかったみたいです。

3 ● rsc
●25ポイント

こちらは参考になるでしょうか。
●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

関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ