2015-05-10
525
У рассмотренного представления есть одна интересная особенность. А именно, если значение поля [Порядок] у одного числа больше соответствующего значения у другого, то первое число обязательно больше второго. Это следует непосредственно из формул перевода (1) и (2) и верно для неотрицательных чисел.
Если порядки равны, то сравниваются мантиссы. Это полностью соответствует обычной системе для целых чисел, когда сравниваются сначала старшие двоичные цифры, затем младшие.
Таким образом, можно интерпретировать числа стандарта IEEE-754 как целые соответствующей длины:
a > b равносильно (ulong)a > (ulong)b, если a, b > 0.
Неприятности начинаются с отрицательными числами. Первый бит равен единице, так что это число будет, как и в случае беззнаковых целых, очень большим положительным. Больше любого по-настоящему положительного.
Если a>0, b<0, то всегда (ulong)a < (ulong)b
С другой стороны, никакого инвертирования битов, как в случае целых чисел со знаком, не производится. Поэтому большее по модулю отрицательное число дает большее в беззнаковой целочисленной интерпретации.
|
|
|
a > b равносильно (ulong)a < (ulong)b, если a, b < 0.
Если запустить RadixSort на массиве: -302 -249 1258 2330 -2948 -543 2398 3263
после сортировки получим: 1258 2330 2398 3263 -249 -302 -543 -2948.
Сначала идут положительные числа, которые отсортировались абсолютно правильно. Затем идут отрицательные, но в обратном порядке!
Все, что необходимо сделать - это передвинуть их на правильное место тем же способом, что и при сортировке целых со знаком, при этом обратив порядок их расположения. Эти изменения можно провести на шаге 3 последнего прохода, работающего со старшими байтами.
Отрицательные числа расположены в обратном порядке, поэтому при вычислении их расположения необходимо идти от count[255]=0, соответствующего наименьшему отрицательному числу до count[128]. При этом в массив нужно записывать сумму всех чисел после текущего, включая само текущее.
s = count[255] = 0; // отрицательные числа располагаются от нуляcp = count+254;for (i = 254; i >= 128; --i, --cp) { *cp += s; s = *cp; }Теперь можно написать окончательную реализацию.
// Функция для последнего прохода при поразрядной сортировке чисел с плавающей точкойtemplate<class T>void floatRadixLastPass (short Offset, long N, T *source, T *dest, long *count) { T *sp; long s, c, i, *cp; uchar *bp; long numNeg=0; for(i=128;i<256;i++) numNeg += count[i]; s=numNeg; cp = count; for (i = 0; i < 128; ++i, ++cp) { c = *cp; *cp = s; s += c; } // изменения, касающиеся обратного расположения отрицательных чисел. s = count[255] = 0; // cp = count+254; // for (i = 254; i >= 128; --i, --cp) {// *cp += s; // остальное - то же, что и в s = *cp; // signedRadixLastPass } bp = (uchar *)source + Offset; sp = source; for (i = N; i > 0; --i, bp += sizeof(T), ++sp) { cp = count + *bp; if (*bp<128) dest[ (*cp)++ ] = *sp; else dest[ --(*cp) ] = *sp; }} // поразрядная сортировка чисел с плавающей точкойtemplate<class T>void floatRadixSort (T* &in, long N) { T *out = new T[N]; ushort i; long *counters = new long[sizeof(T)*256], *count; createCounters(in, counters, N); for (i=0; i<sizeof(T)-1; i++) { count = counters + 256*i; if (count[0] == N) continue; radixPass (i, N, in, out,count); swap(in, out); } count = counters + 256*i; floatRadixLastPass (i, N, in, out,count); delete in; in = out; delete counters;}Для большего удобства можно объединить все полученные сортировки в одну функцию с дополнительным параметром type = {FLOAT, SIGNED, UNSIGNED}, в зависимости от входного типа данных.
