Алгоритм сортировки по основанию двоичного представления в C

Каков наиболее эффективный способ реализации алгоритма Radix-сортировки в C, который сортирует по двоичному представлению (в массиве целых чисел)?

Я хотел бы иметь возможность указать число n, представляющее количество элементов для сортировки, а также значение b, указывающее, сколько двоичных цифр вы хотите интерпретировать как один цифра в алгоритме сортировки, чтобы вы могли варьировать n и b в зависимости от того, насколько велики ваши числа.

Любые предложения, как это реализовать?


c openmp sorting algorithm radix-sort
person Lars Erik Storbukås    schedule 27.02.2015    source источник
comment
Вопрос не показывает каких-либо исследовательских усилий. Пожалуйста, будьте более конкретными.   -  person minorlogic    schedule 27.02.2015
comment
Вы должны пройти алгоритм и попробовать себя в первую очередь.   -  person Prashant    schedule 27.02.2015

Ответы (2)


arrow_upward
1
arrow_downward

Любые предложения, как это реализовать?

#include <string.h>
#include <limits.h>

void radixsort(unsigned int array[], int n, int b)
{
    unsigned int place[n], *a0 = array, *a1 = place, *a;
    int values = 1<<b, start[values+1], bmask = values-1, shift;
    for (shift = 0; shift < sizeof (int) * CHAR_BIT; shift += b)
    {
        int i;
        memset(start, 0, sizeof start);
        for (i = 0; i < n; ++i) ++start[(a0[i]>>shift&bmask)+1];
        for (i = 2; i < values; ++i) start[i] += start[i-1];
        for (i = 0; i < n; ++i) a1[start[a0[i]>>shift&bmask]++] = a0[i];
        a = a0, a0 = a1, a1 = a;
    }
    if (a0 != array) memcpy(array, a0, sizeof place);
}

Оказывается, описание алгоритма rcgldr подходит для этой реализации, за исключением того, что начальные смещения вычисляются только тогда, когда они потребуются.

person Armali    schedule 25.08.2015

arrow_upward
0
arrow_downward

Подход, который я использую, состоит в том, чтобы сделать один проход по данным для создания набора (матрицы) гистограмм количества вхождений битового шаблона в каждом из битовых полей, используемых для сортировки. Это шаг «подсчета» сортировки по основанию. Затем гистограммы преобразуются в смещения начального индекса, начиная с нуля и накапливая сумму отсчетов для каждой записи в наборе гистограмм. Затем для каждого битового поля выполняется сортировка по основанию, от низшего к высшему, с использованием начальных индексов, связанных с этим битовым полем, и с увеличением каждого индекса по мере его использования. Вики-статья:

http://en.wikipedia.org/wiki/Counting_sort

person rcgldr    schedule 27.02.2015