私はアルゴリズムを勉強する初心者です。コンピューター サイエンスの卒業生でもありません。
ただし、線形ソートの非比較アルゴリズムを読んでいるうちに、基数ソートがカウントソートの拡張であることを理解できました。
私が不明なのは、ソートのカウントの制限です。
O(n*logn) 比較を避ける必要がある場合は、カウントソートが目的を果たしているように見えるのに、なぜ基数ソートを使用するのでしょうか?
確かに、はるかに単純な実装のようです。
6403 次
5 に答える
3
誰かがソートする整数のリストをあなたに渡したと想像してください。整数が含まれていること以外は何も知りません。
運が良ければ、リストにはかなり狭い範囲内の数値が含まれている可能性があります。すべて -100 から 100 の間の整数をソートする場合、カウントソートを行うためにそのサイズの配列を作成することはまったく悪くありません。
しかし、1 つの数値でも非常に大きいか非常に小さい場合は、入力全体で並べ替えをカウントするために、配列の境界を拡張する必要があります。可能なすべての整数を本当に並べ替えたい場合 (そして、配列を作成する前に値の範囲がわからない場合は、最初に見つけに行かない限り)、サイズの配列を作成する必要があります2 * max_int(負の整数と正の整数の場合)。 ）。
基数ソートは、数字の範囲 (0 ～ 9) を超えるサイズの配列を作成する必要がないため、優れています。
于 2013-07-14T17:56:04.823 に答える
2
カウント ソート アルゴリズム (基数を含む) は、カウント可能な要素にのみ適用されます。残念ながら、実数は可算ではないため、'float' または 'double' の値を簡単にソートすることはできません。測定された温度のリストを並べ替える必要があると想像してください。
可算量 (整数など) に関しては、配列から要素を取得するのが O(1) であると仮定する基本的な間違いがあります。本当じゃない。サイズ N の配列がある場合、この配列にポインターを設定するコストは O(log(N)) です。つまり、要素 Array[i] にアクセスするには、「i」を定義する必要があり、「i」の値を定義するには、log(i) ビットを設定する必要があります。N が小さい限り (カウント ソートを使用して -100..100 の間の値をソートする場合は 200 とします)、log(N) は一定であると仮定し、それを無視します。しかし、カウント配列よりも整数をソートしたい場合は、大きくなります (サイズ: 2*MAX_INT) log(2*MAX_INT) は大きな数 (32 など) になる可能性があります。サイズが 100 の配列があるとします: A[100] の整数です。O(N*log(N)) ソートを使用するには、O(100*log(100)) 比較が必要です。しかし、カウントソートを使用すると、巨大なサイズのカウント配列を作成します（64ビット整数の場合は2 ^ 64と言います）合計時間はO（N * log（2 ^ 64））で、実際にはO（100 * log（ 100)))。クレイジーに聞こえるかもしれませんが、これは本当です。そして、カウントを開始する前に、カウント配列全体をゼロに設定する必要があるという事実について考えてみてください。これは、O(100*log(100)) 全体よりもはるかに多い 2^64 操作です...そして、大量のメモリの浪費...
結論として、使用するメモリ量が無限であっても、実行時間は実際には O(N) ではありません。実際には、カウント配列をゼロにしてカウントを実行するコストです。
O(MAX_INT) + O(N*log(MAX_INT))
通常、これは妥当な N よりもはるかに大きいO(N*log(N))ため、並べ替えのカウントは実際的ではありません。実用的な唯一のケースは、値の範囲が小さい場合 (-100..100 など) であり、
O(MAX_INT) + O(N*log(MAX_INT))
になるO(200) + O(N*log(200)) ~ O(N)
基数ソートを使用すると、メモリと巨大なカウント配列をゼロにするコストを節約できますが、範囲の数 -X..X には log(X) 桁があり、通常は log(N) よりも大きい log(MAX_INT) がまだあります。ここで、 N はソートする配列のサイズです。
于 2013-07-14T18:17:48.967 に答える
1
私はこれらの答えのいくつかに同意しません。First Radix Sort は double と float をソートできます。私はそれを行いましたが、比較ソートよりもはるかに高速です。
操作については、以前に書いたこの投稿を参照してください。それは常に最良の線形時間ソートになります。
于 2013-07-15T06:40:57.700 に答える
1
カウントソートの複雑さは O(max - min) です。ここで、min、max は、ソートする最小および最大の整数です。この範囲がソートする配列のサイズよりもはるかに大きい場合は、基数ソートの方が優れています。
于 2013-07-14T18:00:00.763 に答える
0
人々がアルゴリズムについて話すとき、彼らは通常、アルゴリズムのパフォーマンスを時間とメモリの要件で表現します。
ご覧のとおり、並べ替えのカウントは優れています。線形時間で実行されます。
ただし、O(N)メモリ要件も必要です。
アルゴリズムを探すとき、メモリと時間の複雑さの間のこのトレードオフがよく見られます。より多くのメモリを使用することで、より良い実行時間を得ることができます。
そのため、カウントソートは時間の複雑さは優れていますが、入力サイズに比例したスペースが必要になるため、ほとんどの場合、使用するのは実用的ではありません.
さらに深刻な問題として、入力する数値の範囲を事前に把握しておく必要があります。確かに、コーディングするのは簡単でエレガントですが、実際に使用する場合は制限があります。
于 2013-07-14T17:49:11.337 に答える