アルゴリズムについて

「手作業によるソート」がレポートの課題として出されました。
「手作業のために効率的なアルゴリズムを考えて提案して分析しなさい」

条件は次の通り: 資料がそれぞれ A4 の紙一枚。見やすい位置に10桁の番号が書かれている。その番号の昇順にソートする。番号の分布については一切不明。二つのケースを想定: 1) 一人で資料5000枚をソート; 2) 20人で資料50000枚をソート。二つのケースに使えるアルゴリズム一つ、又は両ケースに使えるアルゴリズム一つでもよい。分析では O() での計算量 (理由つき) と実際に想定される時間。今まで習ったアルゴリズムとの類似点や相違点、手作業の特徴に考量した点などについても論じる。

何をすれば良いのかが分かりません。少しでも作業の道筋を示していただければ幸いです。
よろしくお願いします。

No.1 ベストアンサー 回答者： ok-kaneto 回答日時： 2012/10/30 20:17

今まで色々なソートのアルゴリズムを習いましたよね？

で、効率的なってことは計算量のできるだけ小さいアルゴリズムを適用すればよいわけです。
O(n^2)よりもO(n log n)の方が効率が良いのは解りますよね？
わざわざ好き好んでバブルソート使うよりも、クイックソートやマージソートを使いますよね？

一人でやる時と、20人でやるとすると似たような手法でやるよりも効率的な方法が見つかると思います。

この回答へのお礼

具体的な計算方法を教えて頂きありがとうございました。
何とか計算できました。

お礼日時：2012/11/20 18:54

No.3 回答者： hashioogi 回答日時： 2012/11/01 09:06

20人で行うということは

ネットワークでつながった20台のPCが並列で動作するようなもの
ですから、通常のアルゴリズムの本に書いてあるような
バブルソートだとかクイックソートだとかとは違ったアルゴリズムが使用できる
ということでしょう。
20人のうちの誰かが指示者になるのかもしれませんが、
指示者の指示の仕方によって効率が変わってくるといういうことでしょう。
指揮者が残りの19人に遊ぶ暇を与えないように指示を出す
のが効率を上げるポイントではないでしょうか。

この回答へのお礼

お礼が遅れて申し訳ありません。
具体的で分かりやすかったです。

お礼日時：2012/11/20 18:55

No.2 回答者： queuerev2 回答日時： 2012/10/31 22:08

実際に紙を用意して試してみてはいかがでしょう。

とはいっても、5000枚では用意するのもソートするのもとても大変なので、とりあえず数十枚程度でしょうか。
そうすれば、手作業ではどの部分に時間がかかるかを理解することができ、手作業の特徴に考慮することもできるのではないでしょうか。

この回答へのお礼

遅れて申し訳ありませんでした。
お手伝い頂きありがとうございました。

お礼日時：2012/11/20 18:55