比較ソート手法の制限

Question

比較ソートは、データの順序付けが必要なほとんどのシナリオで使用されます。マージソート、クイックソート、挿入ソート、その他の比較ソートなどのテクニックは、O（nLog（n））の下限を使用して異なるデータ型と効率を処理できます。

私の質問は

1. ある選別技術ベースの比較のいずれかの制限がありますか？
2. 非比較のソート手法を使用するシナリオはありますか？

歓声

Answer 1

あなたは、多かれ少なかれ自分でそれに答えました。比較ソート手法はO（n Log（n））の下限に限定されています。非比較ソート手法では、この制限がありません。ノンソートアルゴリズムの一般的な問題は、ドメインがよりよく知られていなければならず、そのために比較ベースの技術ほど多用途ではないということです。

Pigeonhole sortは、可能なキー値の数が要素の数に近い限り、非常に高速です。

Answer 2

明らかに、比較ソートの制限は時間係数-some are better than othersですが、十分な大きさのデータセットがあれば、ある時点ではすべてが遅くなりすぎます。そのトリックは、並べ替えるデータの種類と種類を考慮して適切なものを選択することです。

比較しないソートは、データを無視する他の要因に基づいています。例えば、counting sortは、各要素を調べることでデータのコレクションを注文します。コレクション内の他の値と比較することはありません。ソートを数えることは、いくつかのデータに基づいてコレクションを並べ替えるのに便利です。もし整数のコレクションを持っていれば、すべての要素を値1で取り出し、最初にデスティネーションに入れ、次に値2のすべての要素を並べます（ok、それはコレクションをすばやくズームし、値を並べ替えるために "疎"配列を使用しますが、それは基本的な原則です）

Answer 3

なぜ、比較ソートにN log Nの比較が必要なのですか。 Nがあります！私たちが知っているように、ln（N！）はおよそN ln N - N + O（ln N）です。大きなO表記では、N ln Nよりも低い項を無視することができ、lnとlogは定数だけが異なるため、最終結果O（N log N）