Каким должно быть мое постоянное значение маски для сортировки по основанию?

Мне дали задачу для одного из моих курсов CS, где я должен запрограммировать сортировку по основанию LSD, которая может сортировать целые числа без знака (+ или -). Дано, что сортируемые значения являются 32-битными целыми значениями.

Условие состоит в том, что моя маска должна быть постоянным значением, в чем и заключается мой вопрос. Если я выполняю побитовую операцию & над 32-битным целым числом, где каждая цифра представлена ​​4 битами (шестнадцатеричное представление), должна ли моя маска быть 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];
        }
    }
}

Я также хотел бы добавить, что все определенные константы и глобальные переменные являются обязательными, поскольку мне сказали использовать их в моей сортировке по основанию.


c sorting bitmask radix-sort bit-masks
person Erich Hauck    schedule 24.10.2015    source источник
comment
При сортировке по полубайтам (4-битные значения) маска должна быть 0xf, но применяться после сдвига вправо. Bucket_index = (значения[j] ›› (BITS_PER_PASS*i))   -  person rcgldr    schedule 25.10.2015
comment
Вы также можете определить MASK как ((1‹‹BITS_PER_PASS)-1), предполагая, что BITS_PER_PASS меньше количества битов в целом числе.   -  person rcgldr    schedule 25.10.2015
comment
эта строка: int *buckets[NUM_BUCKETS]; объявляет массив из 16 указателей на целые числа. определение указателей не там, где указывают указатели. Поскольку эта строка находится в пространстве file global (которое автоматически инициализируется всеми 0x00), результатом является массив из 16 указателей, каждый из которых содержит NULL.   -  person user3629249    schedule 25.10.2015
comment
продолжение: Эта строка: buckets[j][ bucket_sizes[bucket_index]]=values[j]; - это 1) выбор нулевого указателя, 2) (неправильно) индексация, куда указывает этот указатель (т.е. некоторый индекс вне адреса 0.) Затем записать значение в какое-то небольшое смещение от адреса 0. В целом, вероятно не то, что вы хотите, и почти наверняка вызовет событие ошибки сегмента во время выполнения.   -  person user3629249    schedule 25.10.2015

Ответы (2)


arrow_upward
0
arrow_downward

вместо этого:

int *buckets[NUM_BUCKETS];
int bucket_sizes[NUM_BUCKETS];
...
buckets[j][ bucket_sizes[bucket_index]]=values[j];

предлагать:

int buckets[NUM_BUCKETS];
int bucket_size[NUM_BUCKETS];
...
buckets[bucket_size[bucket_index]]=values[j];

относительно этих строк:

bucket_index = (values[j] & MASK) >> BITS_PER_PASS*i;

Я бы ожидал чего-то, что извлекает 4 бита, например:

bucket_index = (values[j] >> BITS_PER_PASS*i) & MASK;

где MASK будет 0x0F, потому что попытка выбрать один из 16 различных «сегментов» (где &0x0F приведет к значению в диапазоне 0...15)

person user3629249    schedule 25.10.2015
comment
Большое спасибо! Это имеет большой смысл и решает мою проблему. Я попытался проголосовать, но мой аккаунт слишком новый, чтобы сделать его безудержным. - person Erich Hauck; 26.10.2015
comment
Вы должны быть в состоянии «принять» мой ответ на свой вопрос, даже если у вас практически нет «репутации». - person user3629249; 28.10.2015

arrow_upward
0
arrow_downward

Я вижу, вы используете массив с именем Bucket_Sizes[NUM_BUCKETS] и массив указателей. Они могут быть объявлены внутри функции сортировки. Для 32-битных целых чисел без знака NUM_BUCKETS = 32/BITS_PER_PASS.

Вам также понадобится второй буфер для хранения отсортированных значений, например, buffer = malloc(n * sizeof(unsigned int); Не забудьте освободить(buffer) после завершения сортировки.

Массив указателей должен быть установлен следующим образом: Buckets[0] = buffer, Buckets[1] = Buffer + Bucket_Sizes[0], Buckets[2] = Buffer + Bucket_Sizes[0] + Bucket_Sizes[1], ... . Вы можете использовать локальную переменную, чтобы отслеживать суммы размеров сегментов. Обратите внимание, что последний bucket_sizes[15] не используется для установки массива указателей.

После каждого прохода буфер обмена и значения (рассматривая их как указатели). Поскольку это четное количество проходов (8), отсортированные данные вернутся в значения.

person rcgldr    schedule 25.10.2015