比較ソート手法の制限

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

私の質問は

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

歓声

出典

2009-04-26 Arnkrishn

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

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

出典

2009-04-26 22:57:29

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

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

出典

2009-04-26 22:59:43 gbjbaanb

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

出典

2012-07-29 04:14:05

答えて

関連する問題