$ N $ itemの未符号化リストを考えると、リストを並べ替えるには平均して数ランダムな比較が必要ですか。

Question

$ n $ 項目 $ x_1、\ ldots、x_n $ のunsortedリストがあります。リストを並べ替えることができるまで、 $ {n \ select 2} $ 可能なバイナリ比較の可能性（置き換え）。

平均して、これらのランダムな比較のうちの数を並べ替える必要がありますか？

フォローアップの質問：

1. 必要な比較数の分布はどのように見えますか？
2. バイナリの代わりに $ k $ -ARY比較を使用している場合は、答えは何ですか。
3. 交換なしで比較が行われた場合は答えは何ですか（すなわち、あなたは2回同じ比較を受けない）？
4. 比較のセットを考えると、リストがソート可能なかどうかを確認するにはどうすればよいですか。答えはダグとトポロジのソートを作成することですが、私はただ確認したいだけです。

厳密な答えは素晴らしいでしょうが、大きな $ o $ 答えも元気です、私はします。

Answer 1

非対称的には、 $ \ theta（n ^ 2 \ log n）$ 比較。

$ x _ {（1）}、\ dots、x _ {（n）} $ はソート順の要素を表します。その後、 $ x _ {（1）} $ と $ x _ {（2）}の間の比較が表示されない場合$ 、どの順序が表示されるべきかを伝える方法はありません。隣接する要素のすべてのペアについても同じことが同じです。したがって、 $ n-1 $ クーポン（隣接する要素ペアごとに1つ）があり、それらをすべて収集する必要があります。 クーポンコレクタ問題、 $ \ theta（n \ log n）$ 私たち全員を集めた前に、クーポンをランダムに選択しました。各観察には、 $ 2 / n $ クーポンである可能性がありますので、 $ \ theta（n ^ 2 \ log n）$ 観測はすべてのクーポンを収集する前に。すべてのクーポンを収集すると、 $ x $ の並べ替えを行うことができます。クーポンがない場合は、並べ替えできません。

後続の質問は、クーポンコレクターの問題について事実を辞退し、Wikipediaの尾境界を使用して配布に関する情報をバインドすることができます。

交換なしで比較が選択されている場合は、 $ \ theta（n ^ 2）$ 観測値が必要です。

リストがソート可能であるかどうかを確認するための合理的な方法は、トポロジ的にソートされた順序で隣接する項目のすべてのペアの間の比較を観察したことを確認します。