基数C++で並べ替え

Question

整数の基数ソートを行うC++コードを記述しようとしています。チュートリアルのオンラインを見て、各整数を右のバケットに配置しなければならないことがわかりました。最下位から始まります。私の質問は、私は基数ソートのための通常のアルゴリズムで0から9までの10個のバケットが必要ですか？これらのバケットをリンクリスト（例：* list1 ~~~ * list9）として割り当てると、ちょっと変わって見えますか？

ありがとうございます。これは宿題ではなく、ただ好奇心から外れています。

Answer 1

これはC++の質問ではありませんが（Radix SortはC++ではっきりと実装できますが）、少なくともリンクリストとは何の関係もありません。並べ替えは、各桁のバケットに効率的にアクセスできる桁ごとのベースで行われます。このために、リストはあまりうまく動かないかもしれませんが、ベクトルがあります。各バケットの内側にリストを使用することができます。

必要なバケットの数に関しては、答えは次のとおりです。 1より大きい整数ベースを使用することができ、対応するバケット数が必要になります。コンピュータは2の累乗を使って2の累乗を計算すると特に優れているので、10のような他の拠点を使うよりも効率的です。奇妙なことに、Wikipedia's article on Radix Sortはベース10を使用します。おそらく、ベースの自由な選択についてあまりにも多くの混乱を避けるためです。