c/c ++でradix sort for radixの個々の数字を取得する最良の方法

Question

RADIXソートアルゴリズムで使用するためにn桁数を持つINTから個々の数字を取得する最良の方法は何ですか？ C/C ++でそれを行う特に良い方法があるのではないかと思いますが、そうでない場合は、一般的な最良の解決策は何ですか？

編集：明確にするために、私はそれを文字列に変換して数字の配列のように扱う以外の解決策を探していました。

Answer 1

サイズの数字を使用します 2^k. 。を抽出します n数字：

#define BASE (2<<k)
#define MASK (BASE-1)

inline unsigned get_digit(unsigned word, int n) {
    return (word >> (n*k)) & MASK;
}

ShiftとMaskを使用して（2のパワーであるベースで有効になります）、高価な整数診断命令が回避されます。

その後、最適なベースを選択することは、実験的な質問です（特定のハードウェアの時間/スペーストレードオフ）。おそらく k==3 （ベース8）はうまく機能し、バケツの数を制限しますが、 k==4 （ベース16）は、単語のサイズを分割するため、より魅力的に見えます。ただし、単語のサイズを分割しないベースには何の問題もありません。ベース32またはベース64のパフォーマンスが向上していることがわかります。これは実験的な質問であり、キャッシュの動作と配列にある要素の数に応じて、ハードウェアによって異なる可能性があります。

最終注：並べ替えている場合 署名 整数の生活は、署名されたように最も重要なビットを扱いたいので、はるかに大きな痛みです。すべてを署名していないものとして扱うことをお勧めします。そして、本当に署名が必要な場合は、基数のソートの最後のステップでバケツを交換して、最も重要な1のバケツが最も重要なものになります。 絶対に 簡単になります k 単語サイズを分割します。

Answer 2

ベース10を使用しないで、ベース16を使用します。

for (int i = 0; i < 8; i++) {
    printf("%d\n", (n >> (i*4)) & 0xf);
}

整数はバイナリに内部に保存されるため、これは10で割るよりも効率的になります。 小数 数字。