Radix Sort Base 16 (Hexadecimals)

Я потратил больше 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  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 = 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 по этому вопросу, но ни один из них не охватывает детали.

Ваша реализация сортировки radix немного некорректна:

  • он не может обрабатывать отрицательные числа
  • count[] массива 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.

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

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

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

Пример кода, который вы видите, показывает сортировку 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); } 
 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]++; } } } 

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

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

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

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

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