0

CS コースの 1 つで、符号なし整数 (+ または -) をソートできる LSD 基数ソートをプログラムする必要があるという問題がありました。ソートされる値は 32 ビット整数値であるとします。

規定は、私のマスクが定数値でなければならないということです。これが私の質問の場所です。各桁が 4 ビット (16 進表現) で表される 32 ビット整数に対して & ビット演算を行う場合、マスクは 28 にする必要がありますか? （バイナリで28ビットの1が必要なので）

また、追加のエラーに気付く人がいる場合は、注意してください。

#define BITS_PER_PASS 4
#define NUM_PASSES 8
#define NUM_BUCKETS 16
#define MASK 28

int *buckets[NUM_BUCKETS];
int bucket_sizes[NUM_BUCKETS];

void radix_sort( int *values, int n )
{
    int i, j;
    int bucket_index;
    int *p;

    for( i=0; i < NUM_PASSES; i++ )
    {
        for( j=0; j < NUM_BUCKETS; j++ )
        {
            bucket_sizes[j]=0;
        }

        for( j=0; j < n; j++ )
        {
            bucket_index = (values[j] & MASK) >> BITS_PER_PASS*i; //QUESTION
            buckets[j][ bucket_sizes[bucket_index]]=values[j];
            bucket_sizes[bucket_index]++;
        }

        p = values;

        for( j=0; j < NUM_BUCKETS; j++ )
        {
            memcpy((void *)p, (void *)buckets[j], sizeof(int)*bucket_sizes[j]);
            p+=bucket_sizes[j];
        }
    }
}

また、基数ソートでこれらを使用するように言われたため、定義された定数とグローバル変数はすべて必須であることも付け加えておきます。

4

2 に答える 2

0

bucket_sizes[NUM_BUCKETS] という配列とポインターの配列を使用しているようです。これらは sort 関数内で宣言できます。32 ビットの符号なし整数の場合、NUM_BUCKETS = 32/BITS_PER_PASS です。

また、並べ替えられた値を保持するための 2 番目のバッファーも必要です。

ポインタの配列は、buckets[0] = buffer、buckets[1] = buffer + bucket_sizes[0]、buckets[2] = buffer + bucket_sizes[0] + bucket_sizes[1]、... として設定する必要があります。ローカル変数を使用して、バケット サイズの合計を追跡できます。最後のbucket_sizes[15]は、ポインターの配列を設定するために使用されないことに注意してください。

各パスの後、バッファーと値を交換します (それらをポインターとして扱います)。パスの数が偶数であるため (8)、並べ替えられたデータは最終的に値に戻ります。

于 2015-10-25T00:28:06.793 に答える