Поразрядная сортировка целых чисел со знаком
Числа со знаком хранятся абсолютно также, за исключением одной важной детали. А именно, если выписать число в двоичном представлении, то первый бит старшего байта является знаковым.
Рассмотрим short int i = 669110 = 0x1A23 = 00011010'001000112. Здесь старший байт 0x1A, и его знаковый бит выделен. Он равен нулю, так как число положительное.
У отрицательного числа знаковый бит равен 1. При этом все остальные биты числа инвертированы, т.е вместо 0 хранится 1, вместо 1 - ноль. Таким образом, -669110 имеет вид 11100101'110111012.
Внутреннее представление чисел в двоичном виде(байты хранятся в обратном порядке):
Каким образом такое представление влияет на сортировку? Очень просто - все отрицательные числа воспринимаются как очень большие (еще бы, первый бит равен 1) положительные числа.
Если для отрицательных чисел верно |a| > |b|, то, благодаря инвертированным битам, (unsigned)a < (unsigned)b. Поэтому порядок, в котором сортируются такие числа, остается естественным: большее по модулю отрицательное число стоит впереди.
Например, последовательность-302 -249 1258 2330 -2948 2398 -543 3263после сортировки станет такой:1258 2330 2398 3263 -2948 -543 -302 -249.Как видно, и положительные и отрицательные числа отсортировались правильно. Однако, их взаимное расположение необходимо подкорректировать.
Для этого модифицируем последний проход сортировки, работающий со старшими байтами и производящий окончательную расстановку.
Все, что нам необходимо - узнать номер первого отрицательного числа numNeg, и заполнять массив dest сначала числами после numNeg(отрицательными), а потом - остальными(положительными).
Определить по старшему байту знак числа можно без битовых операций, по результатам сравнения.
После шага 1 в count[i] содержится количество байт, равных i. Отрицательных чисел столько же, сколько байт с единичным старшим битом, т.е равных 128...255:
На шаге 3 увеличиваем начальную позицию положительных чисел на numNeg, а отрицательные записываем с начала массива. Это приводит к следующей процедуре:
// проход поразрядной сортировки по старшим байтам,// для целых чисел со знаком Offset = sizeof(T)-1.template<class T>void signedRadixLastPass (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]; // первые 128 элементов count относятся к положительным числам. // отсчитываем номер первого числа, начиная от numNeg s = numNeg; cp = count; for (i = 0; i < 128; ++i, ++cp) { c = *cp; *cp = s; s += c; } // номера для отрицательных чисел отсчитываем от начала массива s = 0; cp = count+128; for (i = 0; i < 128; ++i, ++cp) { c = *cp; *cp = s; s += c; } bp = (uchar *)source + Offset; sp = source; for (i = N; i > 0; --i, bp += sizeof(T) , ++sp) { cp = count + *bp; dest[*cp] = *sp; ++(*cp); }}Соответственным образом изменится и внешняя процедура сортировки. На последнем шаге теперь происходит вызов signedRadixLastPass.
template<class T>void signedRadixSort (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; signedRadixLastPass (i, N, in, out, count); delete in; in = out; delete counters;}
Формат IEEE-754
Особенно подходящим местом применения radixSort является компьютерная графика. Есть много координат, которые необходимо отсортировать, причем с наибольшей скоростью. Поэтому было бы очень удобно распространить возможности процедуры на числа с плавающей точкой.
С другой стороны, существует несколько стандартов для представления таких чисел. Наиболее известным следует признать IEEE-754, который используется в IBM PC, Macintosh, Dreamcast и ряде других систем. Зафиксировав формат представления числа, уже можно модифицировать соответствующим образом сортировку.
Любое число можно записать в системе с основанием BASE как M*BASEn, где |M|<BASE. Например, 47110 = 4.7110 * 102, 6.510 = 6.510*100, -0.003210 = -3.210 * 10-3.
В двоичной системе можно дополнительно сделать первую цифру M равной 1: 101.012 = 1.01012*22, -0.000011 = -1.12*2-5
Такая запись называется нормализованной. M называется мантиссой, n - порядком числа. Стандарт IEEE-754 предполагает запись числа в виде [знак][порядок][мантисса]. Различным форматам соответствует свой размер каждого из полей. Для чисел одинарной точности(float) это 1 бит под знак, 8 под порядок и 23 на мантиссу. Числа двойной точности(double) имеют порядок из 11 бит, мантиссу из 52 бит. Некоторые процессоры(например, 0x86) поддерживают расширенную точность(long double).
| тип/бит | [Знак] | [Порядок] | [Мантисса] | [Смещение] |
| float | ||||
| double |
Рассмотрим числа одинарной точности(float).
Как и в целых числах, значение знакового бита 0 означает, что число положительное, значение 1 - число отрицательное.
Так как первая цифра мантиссы всегда равна 1, то хранится только ее дробная часть. То есть, если M=1.010112, то [Мантисса]= 010112. Если M=1.10112, то [Мантисса]=10112. Таким образом в 23 битах хранится мантисса до 24 бит длиной. Чтобы получить из поля [Мантисса] правильное значение M необходимо мысленно прибавить к его значению единицу с точкой.
Для удобства представления отрицательного порядка в соответствующем поле реально хранится порядок+смещение. Например, если n=0, то [Порядок]=127. Если n=-7, то [Порядок]=120. Таким образом, его значение всегда неотрицательно.
Таким образом, общая формула по получению обычной записи числа из формата IEEE-754:
N = (-1)[Знак] * 1.[Мантисса] * 2[Порядок]-127 (нормализованная запись, 1)
Для 10.2510 = 1010.012 = +1.01001 * 23 соответствующие значения будут [Знак]=0 (+) , [Порядок] = 130(=3+127), [Мантисса] = 010012.
При значениях [Порядок]=1...254 эта система позволяет представлять числа приблизительно от +-3,39*10-38 до +-3,39*10+38.
Особым образом обрабатываются [Порядок]=0 и [Порядок]=255.
Если [Порядок]=0, но мантисса отлична от нуля, то перед ее началом необходимо ставить вместо единицы ноль с точкой. Так что формула меняется на
N = (-1)[Знак] * 0.[Мантисса] * 2-126 (денормализованная запись, 2)
Это расширяет интервал представления чисел до +-1,18*10-38. ... +-3,39*10+38
[Порядок]=0 [Мантисса]=0 обозначают ноль. Возможно существование двух нулей: +0 и -0, которые отличаются битом знака, но при операциях ведут себя одинаково. В этом смысле можно интерпретировать ноль как особое денормализованное число со специальным порядком.
Значение [Порядок]=255(все единицы) зарезервировано для специальных целей, более подробно описанных в стандарте. Такое поле в зависимости от мантиссы обозначает одно из трех специальных "нечисел", которые обозначают как Inf, NaN, Ind, и может появиться в результате ошибок в вычислениях и при переполнении.
Числа двойной точности устроены полностью аналогичным образом, к порядку прибавляется не 127, а 1023. Увеличение длин соответствующих полей позволяет хранить числа от 10-323.3 до 10308.3, значение [Порядок]=2047(все единицы) зарезервировано под "нечисла".