algorithm - 比較ソートよりも非比較ソートを使用する場合

Question

omega(nlogn)クラスでは、すべての比較ベースの並べ替えの下限を回避するために、一連の新しい非比較並べ替えについて学びました。しかし、私にとって少し不明確だったのは、どの種類のソート アルゴリズムをいつ使用するかについての長所と短所です。

非比較ソート アルゴリズム (基数、バケット、キー インデックス) を使用できるように、データ セットを微調整することはできませんか? もしそうなら、比較のポイントは何ですか？

初歩的な質問で申し訳ありませんが、ネットで調べてもわかりません。

Answer 1

アイテムのすべてのセットを調整して、非比較ソートで効率的に使用できるわけではありません。たとえば、任意精度の数値を並べ替えるには、バケットソート内でループを何度も実行する必要があり、パフォーマンスが低下します。

基数ソートの世界の問題は、ソートされるすべてのアイテムのすべての要素を調べなければならないことです。一方、比較ベースの並べ替えでは、かなりの数のサブ要素（数字、文字など）をスキップできます。たとえば、比較関数が2つの文字列をチェックすると、最初の差で停止し、両方の末尾をスキップします。文字列。一方、バケットソートでは、すべての文字列^*のすべての文字を調べる必要があります。

一般に、最良の漸近的複雑さを追跡することは必ずしも良い戦略ではありません。非常に複雑なアルゴリズムを使用すると効果が得られるNの値は、高すぎてより複雑なアルゴリズムを実用化できないことがよくあります。たとえば、クイックソートは時間計算量が非常に悪いですが、オーバーヘッドが非常に低いため、平均して他のほとんどのアルゴリズムよりも優れており、ほとんどの実用的な状況で適しています。

---

^*実際には、バケットソートの実装では、バケット内のアイテム数が特定のしきい値を下回るとすぐに比較ベースのソートに切り替えることで、すべてのサブ要素（数字、文字など）を調べる必要がなくなります。このハイブリッドアプローチは、単純な比較ベースのソートと単純なバケットソートの両方に勝っています。

Answer 2

非比較ベースの並べ替えを作成するのが面倒な場合は、比較ベースの並べ替えを使用します。

比較ベースの並べ替えは本質的に低速です。入力要素に対してコンパレータを何度も呼び出す必要があり、各呼び出しで比較ベースの並べ替えに正確に 1 ビットの情報が提供されます。正しい比較ベースの並べ替えでは、その入力に関する情報を平均して log_2(n!) ~= n log(n) ビット蓄積する必要があります。

これで、すべてのデータがマシンで表現されます。特定の種類のデータ、その表現、および並べ替えに使用しているマシンに合わせて並べ替えアルゴリズムを調整できます。何をしているのかを知っていれば、多くの場合、比較ベースのズボンを打ち負かすことができます。ソートアルゴリズム。

ただし、パフォーマンスがすべてではなく、最もパフォーマンスの高いソリューションが適切なソリューションではない場合があります (実際、私が見たほとんどのケース)。優れた比較ベースの並べ替えでは、ブラック ボックス コンパレータを使用でき、n log(n) 回の小さな定数回で入力を並べ替えます。そして、それはほとんどすべてのアプリケーションにとって十分です.

編集:上記は、入力全体を格納するのに十分な RAM がある場合にのみ実際に内部ソートに適用されます。外部ソート (たとえば、ディスクへのオーバーフロー) は、通常、一度に約半分の RAM フル データを読み取り、非比較ベースのソートを使用して、ソート結果を書き出すことによって実行する必要があります。ソートを入力および出力とオーバーラップするように注意してください。最後に、(比較ベースの) n-way マージを行います。

Answer 3

非比較ベースのソート アルゴリズムは、入力に関する仮定を行います。入力のすべての要素は、線形時間の複雑さを確保するために、一定の長さの範囲内に収まる必要があります。一方、比較ベースの並べ替えアルゴリズムは、入力に関する仮定を行わず、あらゆるケースに対処できます。非比較ベースのソート アルゴリズムは、多くの場合、追加のメモリ コストと入力の一般性の欠如を犠牲にします。

Answer 4

非比較ソートの問題は、その複雑さが通常、入力のサイズ以外のパラメーターに依存することです。たとえば、基数ソートの複雑さは O(kn) です。ここで、k は要素の最大桁数です。問題は、k が n とどのように関係しているかです。k が n とほぼ同じ場合、アルゴリズムは O(n^2) になります。