algorithm - 基数ソートを使用する適切な時期はいつですか？

Question

基数ソートを使用できるようにするためのデータの制約は何ですか？

整数の大きなリストをソートする場合、基数ソートを使用するのが適切でしょうか？基数ソートがこれ以上使用されないのはなぜですか？

Answer 1

なんらかの制約があるキーを持つ大量のデータ セットがある場合に最適です。たとえば、64 ビット数値の 100 万個の配列を並べ替える必要がある場合、最下位 8 ビットで並べ替え、次に次の 8 ビットで並べ替えることができます (8 回適用)。そうすれば、この配列は 1M*log(1M) ではなく、8*1M 操作でソートできます。

Answer 2

整数値の範囲がわかっていて、それが大きすぎない場合は
、 並べ替えをカウントする方が適切な場合があります。

Answer 3

思ったほど頻繁に表示されない理由の 1 つは、基数ソートが比較ベースのソート (クイックソート/マージソート/ヒープソート) ほど汎用的ではないためです。ソートするアイテムを整数または整数のようなものとして表すことができる必要があります。標準ライブラリを使用すると、任意のオブジェクトを比較する比較関数を簡単に定義できます。任意のデータ型を整数に適切にマップするエンコーディングを定義するのは難しいかもしれません。

Answer 4

バケットの並べ替えは、データ項目の数に比べて個別のキー値の数が少ない場合や、元のリストを乱すことなく再並べ替えされたリストのコピーを作成することが目標である場合に役立ちます (そのため、古いリストの新しいバージョンを同時に作成することは負担ではありません)。可能なキーの数が多すぎて 1 回のパスで処理できない場合は、複数のパスを作成してバケット ソートを基数ソートに拡張できますが、バケット ソートが小さなキーに提供できる速度の利点の多くを失います。

一部の外部ソート シナリオでは、特に異なるキー値の数が非常に少なく (たとえば 2 つ)、安定したソートが必要であり、I/O デバイスが 1 つの順次データ ストリームでしか効率的に動作できない場合は、 K がソース データ ストリームを通過するようにします。ここで、K はキー値の数です。最初のパスでは、キーが最小の正当な値であるすべてのアイテムをコピーし、残りをスキップします。次に、キーが次に高い値であるすべてのアイテムをコピーし、残りをスキップします。このアプローチは明らかに恐ろしく効率的です。非常に多くの異なるキー値がある場合ですが、2 つある場合は非常に適しています。