c++ - バケットソートとカウントソートのシナリオ

Question

これはしばらくの間私を混乱させてきました。バケットソートでソートをカウントするよりも使用する必要があるシナリオを知りたいです（またはその逆）。

Answer 1

これらの 2 つのページは、両方の並べ替えに関する情報を提供します。

• カウントソート
• バケットソート

カウントソートについて：

カウントソートは配列へのインデックスとしてキー値を使用するため、比較ソートではなく、比較ソートの Ω(n log n) 下限は適用されません。1バケット ソートは、同様の時間分析を使用して、カウント ソートと同じタスクの多くに使用できます。ただし、カウントソートと比較して、バケットソートでは、各バケット内のアイテムのセットを保持するために、リンクされたリスト、動的配列、または事前に割り当てられた大量のメモリが必要ですが、カウントソートでは、バケットごとに単一の数値 (アイテムの数) が格納されます。[ 4]

バケットソートについて:

バケット ソートは、カウント ソートの一般化と見なすことができます。実際、各バケットのサイズが 1 の場合、バケット ソートはカウント ソートに縮退します。バケット ソートの可変バケット サイズにより、O(M) メモリの代わりに O(n) メモリを使用できます。ここで、M は個別の値の数です。代わりに、ソートの O(n + M) の最悪の場合の動作のカウントをあきらめます。