なぜクイックソート (またはイントロソート)、あるいは比較ベースのソートアルゴリズムが基数ソートよりも一般的なのでしょうか? 特に数値のソートの場合。
基数ソートは比較ベースではないため、O(nよりも高速になる可能性があります。logn) である。実際、これは O(kn) です。ここで、k は各項目を表すために使用されるビット数です。使用するバケットの数を選択でき、必要なメモリがマージソートの要件よりも少ない可能性があるため、メモリのオーバーヘッドは重要ではありません。
それはキャッシュと関係があるのでしょうか? あるいは配列内の整数のランダムなバイトにアクセスしているのでしょうか?
ベストアンサー1
私の頭に浮かぶ議論は2つあります。
クイックソート/イントロソートはより柔軟です:
クイックソートとイントロソートは、あらゆる種類のデータに適しています。ソートに必要なのは、項目を比較できることだけです。これは数値の場合は簡単ですが、他のデータもソートできます。
一方、基数ソートは、バイナリ表現によってソートするだけです。項目同士を比較することはありません。
基数ソートにはより多くのメモリが必要です。
私が見た基数ソートの実装はすべて、部分的なソート結果を格納するためにセカンダリ バッファを使用します。これにより、ソート アルゴリズムのメモリ要件が増加します。数キロバイトをソートするだけなら問題にならないかもしれませんが、ギガバイトの範囲に入ると大きな違いが生じます。
私の記憶が正しければ、インプレース基数ソート アルゴリズムは理論上は存在します。