比較回数が少なくなるソート

質問

大量にある画像に人間が優劣を判定し、その結果をソートしたいです。（順位を付けたい）
画像はすでにデジタルデータ化されてパソコンの中にあります。

二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作（比較の判断）をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか？

ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではｎ(ｎ－１)／２の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。

また、例えばA,B,Cの比較に置いて、
A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。

以上、ご指導のほど、よろしくお願い申し上げます。

回答No.2

MillenniuM · ベストアンサー

比較回数を最小にするという意味なので、
ソーティング・ネットワーク問題に類しています。
この問題は、任意に数については結論が出ていないと思うので、
質問への直接の答えは「ない」ということになるかと思います。
マージソートやクイックソートの比較部を外部化して、
人間へのインターフィスを作るのが現実的かと思います。

お礼

MillenniuMさん、ご回答ありがとうございました。

結論として、ソートの比較演算の部分だけ人間にインターフェィスするようにし、ソートのアルゴリズム自体は言語にお任せという方針にしようと思いました。とても参考になるご意見で、そのように考えるキッカケとなりました。ありがとうございました。

回答No.4

don_go

人間が優劣を判断すると言うのなら挿入ソートが
有効かもしれません。
＃画像に点数を付けて、点数順に並べた画像データ
＃に追加・挿入していく

挿入ソート
＃二分挿入ソート
http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88

お礼

don_goさん、ご回答ありがとうございました。

回答No.3

麻野 なぎ（@AsanoNagi）

この場合、質問の最後にあるような、

> A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つ

という関係が、本当に成り立つかというのが、ひとつのキーになります。

クイックソートというのは、おおざっぱに言えば、

1） ある値をひとつ決める。
2） その値より、「大きいグループ」と「小さいグループ」にグループ分けする
3) それぞれのグループで、同じようにソートをする

という仕掛けです。

たとえば、

1 2 8 4 3 2 だと、適当に4を基準に取ると、

大きいグループ 8
小さいグループ 1 2 3 2

で、小さいグループで、2 を基準に同じことをすると

小さいグループの中の大きいグループ 3
小さいグループの中の小さいグループ 1

で、
1 2 2 3 4 8

とソートができます。
この場合、最初に別れてしまった 1 と 8 は、その後比較されることはありません。

ですから、「大きいグループ」に分類されたデータと、「小さいグループ」に分類されたデータは、このあと、比較されることがありません。

比較回数の少ないソートというのは、こういう風に、「A＞B、B＞C ならば、A＞C」ということが成り立つという前提で、自明な比較を避けるようにしているのです。

お礼

AsanoNagiさん、ごかいとうありがとうございました。

＞自明な比較を避けるようにしているのです。
知りたかった回答です。

とても参考になりました。ありがとうございました。

回答No.1

ok-kaneto

比較回数が少ないのはクイックソートやマージソートです。
ランダム性が高ければクイックソートですが、クイックソートの最悪の場合を考慮するとマージソートの方が優秀です(ただしメモリ使用量が大きい)。 どちらも実装はそれほど難しくありません。

ただ、画像の優劣そのものを人間が判断するとなると少々面倒かもしれません。
同じデータ同士の比較をすることもありますので、ある時はA>Bとなったのが次の比較でA<Bとなってはソートすることができません。人間が判断することのブレが無いことが前提です。

http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88#.E3.82.BD.E3.83.BC.E3.83.88.E3.82.A2.E3.83.AB.E3.82.B4.E3.83.AA.E3.82.BA.E3.83.A0.E3.81.AE.E4.B8.80.E8.A6.A7

補足

ok-kanetoさん、ご回答ありがとうございます。

＞比較回数が少ないのはクイックソートやマージソートです。
比較回数はn*log2nなのでｎ(ｎ－１)／２のものより小さいって事ですよね。

人間の判断のゆらぎについては考慮しなくてOKです。そういう前提です。

質問の最後にふれた「A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つのですが、」
についてですが、クイックソートおよびマージソートでは、A＞B、B＞Cの比較後に比較せずとも結論のでているAとCの比較するような局面はあるのでしょうか？　あるとした場合、比較処理は人間に要求するのではなく、プログラムにやらせたいので、その部分の実装を考慮したいのです。プログラム的な実装が難しいかどうかは問題ではなく、判断する人間の労力を最小限にしたいのが目的です。

もしかするとソートという考えよりも総当たりトーナメントで最下位まで順位を付ける為に最も効率の良い試合の組み合わせは？　という質問の方が良いのかもしれません。