バイナリ選択のための並べ替えアルゴリズム

Question

私が好きな程度に注文したい本のリストを想像してみてください。個々の本を評価する代わりに、リストから2つの書籍（無作為に選んだもの）を選び、必要な数だけ繰り返します（すべての組み合わせを評価しない）。

このバイナリ選択に基づいてブックリストを並べ替えるにはどうすればよいですか？この問題は正式な名前ですか？

Answer 1

Fisher–Yates shuffleの本を2つずつ2つずつ入手できます。ちょうど2つのインスタンスを比較することは、並べ替えと呼ばれるストレッチか、まさにコアであると言えるでしょう。

Answer 2

Jonas Elfströmが指摘しているように、Fisher-Yatesはセットをシャッフルする標準的な方法です。これは、すべてのアイテムのデータを取得できるようになるため、おそらく良い考えです。私はあなたがおそらく1つ以上のパスをしたいと思う。基本的には、アイテムのコレクションをソートするときに、ノードがアイテムであり、エッジが関係が以上である有向グラフを構築しています。アルゴリズム的にこの関係を定義することができれば、1回のパスで十分であり、あなたはよく整理されたセットで終わるでしょう。

ここで合併症は、一度に2つの本を見て、人間がよく定義されたアルゴリズムなしで決めると、A> B、B> CおよびCの状況に終わることは非常に信じられます> A.これは明らかに順序付けられたセットを生成しません。さらに悪いことに、2つの異なる日に、同じ2つの本に対して2つの異なる答えを与えることができる。

私が考えることができる最もよい方法は、n x n行列を維持することです。ここで、nはソートするアイテムの量です。 i, jエントリは、アイテムiがアイテムjよりも良いと選択された回数です。ここでは、iのインデックス行とjのインデックス列です。

ここから、残念なことに特許を得たが理想的です。全くエレガントではありませんが、十分に良いのは、aijとajiの差を合計し、それに基づいて本を並べ替えることです。だから、例えば、3冊

A B C 
    _ _ _ 
A|0 3 2 
B|2 0 3 
C|1 2 0 

をソートすることはAがより優れてB 3倍、より良いよりC 2倍と評価されたことを意味します。行を合計すると、そこで彼らがA > B > Cとして並べ替えます

A: (AB - BA) + (AC - CA) = (3 - 2) + (2 - 1) = 2 
B: (BA - AB) + (BC - CB) = (2 - 3) + (3 - 2) = 0 
C: (CA - AC) + (CB - BC) = (1 - 2) + (2 - 3) = -2 

を与えます。

---

あなたはページランクを使用しない場合は、マトリックスを排除し、各書籍のために0に初期化された整数を関連付けることによって、同一の結果を得ることができます。 AがBより選択されている場合は、Aに関連付けられた整数を増やし、Bに関連付けられた整数を減分します。

^{1私はあなたが本質的に数学的な結果であることをどのように特許をしているか知っています。}

Answer 3

古い質問を残して申し訳ありませんが、これはあなたにとって便利だと思います。

同じ作業をしていたときに、オンライン挿入の並べ替えを選択しました。これは小さなコレクションで完璧な選択です。たとえば、10冊の書籍については、平均14件の比較しかしないでください。最良の場合は、コレクションがすでにソートされている場合にのみ、9回の比較を行う必要があります。

クイックソートを選択した場合は、20回の比較（平均）を実行する必要がありますが、コレクションごとにすべての書籍と比較することで、常に汚れたソートが改善されます。

とにかく、オンラインランキング（以前の比較結果に基づいて次のペア選択）を行う必要があります。

推移関係については、book1とbook2、book2の方がbook3より良く、book1がbook3よりも優れていればbook3より良いと推測されます。それがあなたのために働いていない場合 - それらをランク付けすることはできません。あなたが言うとき、「ランダムに選ばれた、」あなたはあなたの本が選ばれているものの上に選択肢がないことを
http://en.wikipedia.org/wiki/Insertion_sort
http://en.wikipedia.org/wiki/Quick_sort