algorithm - 数値インデックスを使用できる場合の並べ替えの最適な方法は?

Question

ほとんどの場合、ソートには汎用の組み込みライブラリを使用します。しかし、ほとんどの場合、数値インデックスまたはインデックスに変換できるその他の値に基づいて並べ替えを行っています。私が間違っていなければ、数字の並べ替えは O(n) です。では、数値ソート アルゴリズムをまったく使用していないのはなぜでしょうか。

Answer 1

基本的に、比較ベースのソート アルゴリズムを使用します。比較機能を提供し、データを並べ替えることができることは、エンジニアリングの観点からは大きなメリットです。たとえスピード ヒットで支払ったとしてもです。

O(n log n) 比較ベースの並べ替え境界では、合計実行時間ではなく、比較がカウントされることに注意してください。たとえば、文字列を並べ替える場合、比較対象の文字列の長さに比例して比較に時間がかかることがあります。

よくある誤解 (他の回答にも反映されていると思います) は、適度な数の長い数値を並べ替えている場合、比較ベースの並べ替えがより高速な漸近的複雑性を持つようになるというものです。それらはそれぞれkバイトだと言います。これは正しくありません。O(kn log n) の全体的な複雑さに対して、それぞれが O(k) 時間かかる約 n log(n) 数の比較を行います。これはO(kn) よりも悪いです。

高速な基数ソートを設計することは、理論が言うよりも少し難しいです。理論では、できるだけ大きな基数を選択する必要がありますが、選択する基数と、入力ストリームを分割するときに達成する局所性との間にはトレードオフがあります。基数が大きいほど、パスが少なくなりますが、メモリのローカル使用量も少なくなります。