Radix Sort Base 16 (Hexadecimals)

Question

Я потратил больше 10 часов + при попытке отсортировать следующие (шестнадцатеричные) в сортировке LSD radix, но не помогло. В Интернете очень мало материала по этому вопросу.

0 4c7f CD80 41fc 782c 8b74 7eb1 9a03 AA01 73f1

Я знаю, что я должен маскировать и выполнять битовые операции для обработки каждой шестнадцатеричной цифры (4 бита), но не имею ни малейшего представления о том, как и где ,

Я использую код (я понимаю) от GeeksforGeeks

void rsort(int a[], int n) { 
    int max = getMax(a, n); 
    for (int exp = 1; max/exp > 0; exp *= 10) { 
     ccsort(a, n, exp); 
    } 
} 

int getMax(int a[], int n) { 
    int max = a[0]; 
    int i = 0; 
    for (i = 0; i < n; i++) { 
     if (a[i] > max) { 
      max = a[i]; 
     } 
    } 
    return max; 
} 

void ccsort(int a[], int n, int exp) { 

    int count[n]; 
    int output[n]; 
    int i = 0; 

    for (i = 0; i < n; i++) { 
     count[i] = 0; 
     output[i] = 0; 
    } 
    for (i = 0; i < n; i++) { 
     ++count[(a[i]/exp) % 10]; 
    } 
    for (i = 1; i <= n; i++) { 
     count[i] += count[i - 1]; 
    } 
    for (i = n - 1; i >= 0; i--) { 
     output[count[(a[i]/exp) % 10] - 1] = a[i]; 
     --count[(a[i]/exp) % 10]; 
    } 
    for (i = 0; i < n; i++) { 
     a[i] = output[i]; 
    } 
} 

Я также проверил все StackOverflow по этому вопросу, но ни один из них не покрывает детали.

Answer 1

void int_radix_sort(void) { 
    int group; //because extracting 8 bits 
    int buckets = 1 << 8; //using size 256 
    int map[buckets]; 
    int mask = buckets - 1; 
    int i; 
    int cnt[buckets]; 
    int flag = NULL; 
    int partition; 
    int *src, *dst; 

    for (group = 0; group < 32; group += 8) { 
     // group = 8, number of bits we want per round, we want 4 rounds 
     // cnt 
     for (int i = 0; i < buckets; i++) { 
      cnt[i] = 0; 
     } 
     for (int j = 0; j < n; j++) { 
      i = (lst[j] >> group) & mask; 
      cnt[i]++; 
      tmp[j] = lst[j]; 
     } 

     //map 
     map[0] = 0; 
     for (int i = 1; i < buckets; i++) { 
      map[i] = map[i - 1] + cnt[i - 1]; 
     } 

     //move 
     for (int j = 0; j < n; j++) { 
      i = (tmp[j] >> group) & mask; 
      lst[map[i]] = tmp[j]; 
      map[i]++; 
     } 
    } 
} 

После нескольких часов исследований я столкнулся с ответом. Я все еще не понимаю, что происходит в этом коде/ответе. Я не могу заставить свою голову обернуться вокруг концепции. Надеюсь, кто-то может объяснить.

Answer 2

Существует более простой способ реализации сортировки radix. После проверки макс найдите самую низкую мощность 16> = максимальное значение. Это можно сделать с max >> = 4 в цикле, увеличивая x, так что, когда max переходит в ноль, тогда 16 к мощности x составляет> = исходное максимальное значение. Например, max 0xffff потребует 4 прохода с шестью проходами, тогда как максимум 0xffffffff будет принимать 8 проходов на сортировку по методу radix.

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

Пример кода, который вы показываете, представляет собой сортировку радиуса, которая сканирует массив назад из-за того, как счетчики преобразуются в индексы. Этого можно избежать, используя альтернативный метод преобразования индексов в индексы. Ниже приведен пример базовой сортировки по 256 меток для 32-битных целых чисел без знака. Он использует матрицу индексов/индексов, так что все 4 строки счетчиков генерируются только с одним проходом чтения массива, за которым следуют 4 прохода счисления счисления (так что отсортированные данные заканчиваются в исходном массиве). std :: swap - это функция C++ для замены указателей, для C-программы это можно заменить заменой указателей inline. t = a; a = b; b = t, где t имеет тип uint32_t * (ptr для беззнакового 32-битного целого). Для базовой 16-радичной сортировки размер матрицы будет [8] [16].

// a is input array, b is working array 
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // count/index matrix 
size_t i,j,m,n; 
uint32_t u; 
    for(i = 0; i < count; i++){   // generate histograms 
     u = a[i]; 
     for(j = 0; j < 4; j++){ 
      mIndex[j][(size_t)(u & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    for(j = 0; j < 4; j++){    // convert to indices 
     m = 0; 
     for(i = 0; i < 256; i++){ 
      n = mIndex[j][i]; 
      mIndex[j][i] = m; 
      m += n; 
     }  
    } 
    for(j = 0; j < 4; j++){    // radix sort 
     for(i = 0; i < count; i++){  // sort by current lsb 
      u = a[i]; 
      m = (size_t)(u>>(j<<3))&0xff; 
      b[mIndex[j][m]++] = u; 
     } 
     std::swap(a, b);    // swap ptrs 
    } 
    return(a); 
} 

Answer 3

Ваша реализация поразрядной сортировки немного неправильно:

• он не может справиться с отрицательными числами
• массив count[] в функции ccsort() должны иметь размер 10 вместо n. Если n меньше 10, функция не работает.
• Цикл для подсчета количества импульсов идет на один шаг слишком далеко: for (i = 1; i <= n; i++). И снова оператор <= вызывает ошибку.
• Вы говорите, что сортируете по шестнадцатеричным цифрам, но код использует десятичные цифры.

Вот (слегка) улучшенная версия с пояснениями:

void ccsort(int a[], int n, int exp) { 

    int count[10] = { 0 }; 
    int output[n]; 
    int i, last; 

    for (i = 0; i < n; i++) { 
     // compute the number of entries with any given digit at level exp 
     ++count[(a[i]/exp) % 10]; 
    } 
    for (i = last = 0; i < 10; i++) { 
     // update the counts to have the index of the place to dispatch the next 
     // number with a given digit at level exp 
     last += count[i]; 
     count[i] = last - count[i]; 
    } 
    for (i = 0; i < n; i++) { 
     // dispatch entries at the right index for its digit at level exp 
     output[count[(a[i]/exp) % 10]++] = a[i]; 
    } 
    for (i = 0; i < n; i++) { 
     // copy entries batch to original array 
     a[i] = output[i]; 
    } 
} 

int getMax(int a[], int n) { 
    // find the largest number in the array 
    int max = a[0]; 
    for (int i = 1; i < n; i++) { 
     if (a[i] > max) { 
      max = a[i]; 
     } 
    } 
    return max; 
} 

void rsort(int a[], int n) { 
    int max = getMax(a, n); 
    // for all digits required to express the maximum value 
    for (int exp = 1; max/exp > 0; exp *= 10) { 
     // sort the array on one digit at a time 
     ccsort(a, n, exp); 
    } 
} 

выше версия вполне неэффективен из всех подразделений и по модулю операций. Выполнение на шестнадцатеричных цифр можно сделать с помощью сдвигов и масок:

void ccsort16(int a[], int n, int shift) { 

    int count[16] = { 0 }; 
    int output[n]; 
    int i, last; 

    for (i = 0; i < n; i++) { 
     ++count[(a[i] >> shift) & 15]; 
    } 
    for (i = last = 0; i < 16; i++) { 
     last += count[i]; 
     count[i] = last - count[i]; 
    } 
    for (i = 0; i < n; i++) { 
     output[count[(a[i] >> shift) & 15]++] = a[i]; 
    } 
    for (i = 0; i < n; i++) { 
     a[i] = output[i]; 
    } 
} 

void rsort16(int a[], int n) { 
    int max = a[0]; 
    for (int i = 1; i < n; i++) { 
     if (a[i] > max) { 
      max = a[i]; 
     } 
    } 
    for (int shift = 0; (max >> shift) > 0; shift += 4) { 
     ccsort16(a, n, shift); 
    } 
} 

Это будет примерно в два раза быстрее, чтобы отсортировать один байт в то время, с count массив из 256 записей. Также было бы быстрее вычислить подсчеты для всех цифр за один проход, как показано в ответе rcgldr.

Обратите внимание, что эта реализация по-прежнему не может обрабатывать отрицательные числа.

Answer 4

Я вижу ваши баллы. Я думаю, что отрицательные числа легко сортировать после того, как список был отсортирован с чем-то вроде цикла, флага и свопа. wb неподписанные поплавковые точки? - itproxti 1 ноября '16 в 16:02

Что касается обработки с плавающей точек там может быть способом, например, 345,768 это число, оно должно быть преобразовано в целое, то есть сделать его 345768, я умножил 1000 с ним. Так же, как смещение перемещает числа -ve в + ve domain, поэтому умножение на 1000, 10000 и т. Д. Превратит поплавки в числа с их десятичной частью как все нули. Затем они могут быть введены как int или long. Однако при больших значениях целое реформированное число не может быть размещено во всем int или long range.

Число, подлежащее умножению, должно быть постоянным, как и смещение, чтобы соотношение между величинами сохранялось. Его лучше использовать полномочия 2, такие как 8 или 16, так как тогда может использоваться оператор смещения бит. Однако точно так же, как вычисление смещения занимает некоторое время, так и вычисление множителя займет некоторое время. Весь массив должен быть найден для вычисления наименьшего числа, которое при умножении превратит все числа с нулями в десятичные части.

Это может не быстро вычислить, но при необходимости выполнить работу.