なぜQuicksortはRadix-Sortよりも人気があるのですか？

Question

なぜQuickSort（または内臓）、または比較ベースのソートアルゴリズムがRadix-Sortよりも一般的なのですか？特に数字の並べ替えについて。

Radix-Sortは比較ベースではないため、O（nよりも高速になる可能性があります。logn）。実際、それはoです（kn）、kは各アイテムを表すために使用されるビット数です。また、メモリオーバーヘッドは重要ではありません。なぜなら、使用するバケットの数を選択する可能性があり、必要なメモリはMergesortの要件よりも少ない場合があるためです。

キャッシュに関係していますか？または、アレイ内の整数のランダムなバイトにアクセスするかもしれませんか？

Answer 1

2つの議論が私の頭に浮かぶ：

1. QuickSort/Introsortはより柔軟です：

   QuickSortと内ソートは、あらゆる種類のデータでうまく機能します。ソートに必要なのは、アイテムを比較する可能性だけです。これは数字で些細なことですが、他のデータも並べ替えることができます。

   一方、RADIXソートは、バイナリ表現によって物事をソートするだけです。アイテムを互いに比較することはありません。

2. RADIXソートには、より多くのメモリが必要です。

   私が見たすべてのRADIXソート実装は、セカンダリバッファーを使用して部分的なソート結果を保存します。これにより、ソートアルゴリズムのメモリ要件が増加します。キロバイトを2、3個しか並べない場合は問題ではないかもしれませんが、ギガバイトの範囲に入ると大きな違いが生じます。

   ただし、適切に覚えている場合は、紙にRadix-Sortアルゴリズムが存在します。

Answer 2

明らかな答えの1つは、QuickSortを使用して任意のタイプをソートできること（つまり、比較可能なものはすべて）であり、RADIXのみにのみ数字に制限されているということです。そして、IMO Quicksortはより直感的です。

Answer 3

RADIXソートは、（ほとんどの）実世界のユースケースで遅くなります。

理由の1つは、アルゴリズムの複雑さです。

アイテムが一意の場合、k> = log（n）。アイテムが重複していても、k <log（n）が小さい問題のセット。

もう1つは実装です。

追加のメモリ要件（自己は不利な点）は、キャッシュのパフォーマンスに悪影響を及ぼします。

標準的なライブラリのような多くのライブラリは、QuickSortを使用していると言っても安全だと思います。 「困難な実装」や「直感的ではない」が主要な要因ではないと思います。

Answer 4

述べたように ウィキペディア

他のソートアルゴリズムと比較したRADIXソートの効率のトピックはややトリッキーであり、非常に多くの誤解の影響を受けます。 RADIXソートが同等に効率的であるか、効率が低いか、最良の比較ベースのアルゴリズムよりも効率的であるかは、行われた仮定の詳細に依存します。 RADIXソート効率は、d以下の桁を持つnキーの場合はO（D・N）です。 Dが定数として提示されることがあります。これにより、最良の比較ベースのソートアルゴリズムよりも（n・log（n））比較数の比較数である最良の比較ベースのソートアルゴリズムよりも（十分に大きなn）並べ替えが良くなります。ただし、一般に、Dを定数と見なすことはできません。 特に、すべてのキーが明確であるという一般的な（ただし暗黙の）仮定の下では、Dは少なくともlog（n）の順序でなければなりません。 log（n））. 。これは、最良の比較ベースのソートとして、最大の効率的なRADIXをソートにするように思われます（キーがログ（n）よりもはるかに長い場合は、さらに悪いことです）。

カウンター引数は、比較ベースのアルゴリズムは、実際の時間の複雑さではなく、比較数で測定されることです。一部の仮定では、比較は平均して一定の時間になり、他のものではそうではありません。ランダムに生成されたキーの比較は平均して一定の時間がかかります。キーは、最初のビットが半分で異なり、残りの半分の半分で2番目のビットで異なるため、平均2ビットの2ビットになります。比較する必要があります。ソートアルゴリズムでは、最初の比較がランダム性条件を満たしますが、ソートが進むにつれて、比較されるキーは明らかにランダムに選択されなくなります。たとえば、ボトムアップマージソートを検討してください。最初のパスはランダムキーのペアを比較しますが、最後のパスはソート順に非常に近いキーを比較します。

決定要因は、キーの分布方法です。 RADIXソートの最良のケースは、それらが連続したビットパターンとみなされることです。これにより、キーができる限り短くなりますが、それでも鍵は明確であると仮定します。これにより、RADIXはO（n・log（n））をソートしますが、比較ベースのソートは、この仮定の下で一定の時間ではないため、それほど効率的ではありません。代わりに、キーが一定のk> 1とベース2ログの長さk・log（n）のビットパターンであり、それらが均一にランダムであると仮定した場合、radixのソートはまだo（n・log（n）です）、しかし、比較ベースのソートも同様です。「余分な」長さは、ソートされた結果で連続しているキーでさえも十分に異なるため、比較は平均して一定の時間です。 キーがO（log（n））よりも長いがランダムな場合、ラジックスのソートは劣っています。 同様に行うことができる他の多くの仮定もあり、ほとんどの場合、正しい比較をするために慎重な研究が必要です。

Answer 5

他の回答で作成されたポイントは有効ですが、いくつかのコメントで言及されているあなたの懸念に関する限り

...数字のデフォルトのソートアルゴリズムがQuickSortを使用して実装されているという事実。特に図書館の実装...

QuickSortは「安全な」選択肢です。カウントソートに基づいた基数ソートの潜在的なランタイムは非常に魅力的ですが、RADIXソートは悪意のある/不幸なデータセットでの実行が不十分であるためにサブセプトしやすいです。ソートされているキーの数字の数がソートされているキーの数に近づいている場合、Radixソートはn^2で機能しないスペースの複雑さとともに実行され、数値以外のランタイム定数以外の定数がかなり高い傾向がありますソートされているキーの数字の。
Mergesortは、その動作が、ある意味では、各機会に最適なピボットを選択するクイックソート（中央値）に類似しているため、魅力的です。ただし、かなりのスペースの複雑さが伴います。それは、RADIXほど悪意のある/不幸なデータにサブセプトしやすいものではなく、魅力的なランタイムを提供しません。基本的なクイックソートは、ほとんど（または完全に）ソートされたデータセットを除くほとんどのデータセットで非常にうまく機能し、小さなスペースの複雑さが伴います。
QuickSortの脆弱性は、ランダム化されたクイックソートに変換することで簡単に対処できます。 RADIX SORTの脆弱性は、ソートされているキーに制限を配置することにより解決されます。これにより、ライブラリのユーザーが本質的に制限されます。 QuickSortは、小さなデータセットでマージよりもパフォーマンスが高く、マージがより速くなる可能性がある場合は合理的に実行されます。
ライブラリを実装するときは、一般的に有用にする必要があります。これらの例、Webアプリケーション、および非常に制限されたマイクロコントローラーを備えた小さなデバイスをご覧ください。 Webアプリケーションは、定期的に悪意のあるデータに対処する必要があり、さまざまなニーズもあります。前処理された制限を備えたライブラリは、有用である可能性が低くなります。マイクロコントローラーの場合、それはスペースに限定されており、保存できるわずかなビットを放棄することができない場合があります。 QuickSortはスペースを節約し、状況が遅くなると状況が発生した場合、一定の乗数によってのみ遅くなります。
要約 -
1.）ライブラリは、多くの場合、できるだけ多くの一般的な使いやすさのためにコーディングされます
2.）良好なパフォーマンスはすべて受け入れられます。特に、多くの場合、最高のパフォーマンスがある場合、
3.）スペースは常に主要な問題ではありませんが、そうである場合、それはしばしば明示的に制限されます。

Answer 6

RADIX SORTの効率= O（CN）ここで、C =入力キーセットの中で最も高い数字数。 n =入力キーセットのキー数。

Quick Sortの最高のケース= O（n。Logn）ここで、n =入力キーセットのキー数。

それぞれ6桁でソートされる16の数値を想定してください：

RADIX SORT = 16 * 6 = 96時間単位。クイックソート= 16 * 4 = 64時間単位。

レッスン：「C」が少ない場合、RADIXが勝ちます。それが高いとき、それは負けます。クイックソートはキー内の数字数から独立しており、それがやや良くなり、実際に受け入れられるようにします