比較ベースのアルゴリズムでは、5 つの要素をソートするのに 7 回のパスが必要だと言われるのはなぜですか?

結果のソートアルゴリズムの唯一の要件は、オペランドが全順序関係を満たすことです。

1. a≤b かつ b≤c の場合、a≤c (推移性)。
2. a または b については、a≤b または b≤a のいずれかです (完全性)。

この質問には情報理論を使って答えることができます。

1 から 5 までの数字を 1 つ選び、それを推測してもらいます。各ラウンドで質問すると、私の答えは「はい」または「いいえ」(1 または 0) です。数字を推測できると保証するには、何ラウンド必要ですか?

このゲームをもっと楽しくプレイするには、まず自分のラッキーナンバー（たとえば私の場合は 7）から推測し、1 つずつ「それは X ですか？」と聞いてみてください。運が良ければ 1 ラウンドで正解できるかもしれませんが、最悪の場合 5 ラウンドかかることもあります。そのため、答えは「少なくとも 5 ラウンド」にする必要があります（実際には、少なくとも 1 ラウンドで正解できる「かもしれませんが」、正解を「確実に」当てるためには、妥協して 5 と答える必要があります）。つまり、この推測方法の最適な下限は 5 です。 （平均パフォーマンスは1×1/5+2×1/5+…+5×1/5=（1+…+5）/5 = 3）

しかし、バイナリのやり方を知っているので、「3より大きいですか？」と尋ねるでしょう...そして、どの数字を選んでも、3ラウンドしかかかりません。バイナリ検索は明らかに優れた戦略ですが、何が優れているのでしょうか? 情報理論を使用して理解する：最大エントロピー。

英語版Wikipediaのエントリには、大まかな説明があります: Comparison_sort、最小回数はlog(5!) = 6.91で、これは7に丸められます。

決定木は次のようになります。

マージソートを使用する場合、比較の回数は O(nlogn) になります。これは、マージソートがグローバルな最適解であるためですが、ローカルではマージが常に最適であるとは保証されないためです。

クイックソートの GIF を添付します:

[[110233]]

元のリンク: http://justjavac.com/other/2013/04/10/why-any-sort-algorithm-based-on-the-comparison-of-the-five-elements-are-needed-7-times.html