2015-05-10
756
Числа со знаком хранятся абсолютно также, за исключением одной важной детали. А именно, если выписать число в двоичном представлении, то первый бит старшего байта является знаковым.
Рассмотрим 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;}
