Поразрядная сортировка( Radix sort)

он совсем не использует сравнений сортируемых элементов.
Во-вторых, ключ, по которому

происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам...

До сортировки необходимо знать два параметра: k и m, где
k - количество разрядов в самом длинном ключе
m - разрядность данных: количество возможных значений разряда ключа

При сортировке русских слов m = 33, так как буква может принимать не более 33 значений. Если в самом длинном слове 10 букв, k = 10.
Аналогично, для для шестнадцатиричных чисел m=16, если в качестве разряда брать цифру, и m=256, если использовать побайтовое деление.
Эти параметры нельзя изменять в процессе работы алгоритма. В этом - еще одно отличие метода от вышеописанных.

k-разрядные десятичные числа, разрядность максимального числа известна заранее.

Обозначим d(j,n)

- j-ю справа цифра числа n, которую можно выразить как
d(j,n) = [ n / 10j-1 ] % 10

Пусть L0, L1,..., L9 - вспомогательные списки (карманы), вначале пустые.

Поразрядная сортировка состоит из двух процессов, называемых распределение и сборка и выполняемых для j=1,2,...,k.

Фаза распределения разносит элементы L по карманам: элементы li списка L последовательно добавляются в списки Lm, где m = d(j, li). Таким образом получаем десять списков, в каждом из которых j-тые разряды чисел одинаковы и равны m.

Фаза сборки состоит в объединении списков L0, L1,..., L9 в общий список L = L0 => L1 => L2 => ... => L9

на входном списке 0 => 8 => 12 => 56 =>

7 => 26 => 44 => 97 => 2 => 37 => 4 => 3 => 3 => 45 => 10.

Максимальное число содержит две цифры, значит, разрядность данных k=2.

Первый проход, j=1.     Распределение по первой справа цифре: L0: 0 => 10        // все числа с первой справа цифрой 0 L1: пусто L2: 12 => 2 L3: 3 => 3 L4: 44 => 4 L5: 45 L6: 56 => 26 L7: 7 => 97 => 37 L8: 8 L9: пусто         // все числа с первой справа цифрой 9     Cборка:  соединяем списки Li один за другим L: 0 => 10 => 12 => 2 => 3 => 3 => 44 => 4 => 45 => 56 => 26 => 7 => 97 => 37 => 8

цифре: L0: 0 => 2 => 3 => 3 => 4

=> 7 => 8 L1: 10 => 12 L2: 26 L3: 37 L4: 44 => 45 L5: 56 L6: пусто L7: пусто L8: пусто L9: 97     Cборка:  соединяем списки Li один за другим L: 0 => 2 => 3 => 3 => 4 => 7 => 8 => 10 => 12 => 26 => 37 => 44 => 45 => 56 => 97

значений элемента списка.
Сортировку можно организовать так, чтобы не использовать дополнительной

памяти для карманов, т.е элементы списка не перемещать, а с помощью перестановки указателей присоединять их к тому или иному карману.

В представленной ниже программе функция radix_list реализует поразрядную сортировку связанного линейного списка (указатель l), в котором содержатся t-разрядные десятичные положительные числа, без использования дополнительной памяти.

Параметры head[i], tail[i] указывают соответственно на первый и на последний элементы кармана Li. При этом сами карманы являются "виртуальными", память под них не выделяется.

val;
struct slist_ *next;
} slist;

// функция сортировки возвращает указатель

на начало отсортированного списка
slist *radix_list(slist *l, int t) {
// t - разрядность (максимальная длина числа)
int i, j, d, m=1;
slist *temp, *out, *head[10], *tail[10];
out=l;

for (j=1; j<=t; j++) {
for (i=0; i<=9; i++)
head[i] = (tail[i]=NULL);

while ( l != NULL ) {
d = ((int)(l->val/m))%(int)10;
temp = tail[d];
if ( head[d]==NULL ) head[d] = l;
else temp->next = l;
temp = tail[d] = l;
l = l->next;
temp->next = NULL;
}
for (i=0; i<=9; i++)
if ( head[i] != NULL ) break;
l = head[i];
temp = tail[i];
for (d=i+1; d<=9; d++) {
if ( head[d] != NULL) {
temp->next = head[d];
temp = tail[d];
}
}
m*=10;
}
return (out);
}

реорганизовывать,
объединять и т.п. Как применить ту же идею для

массивов ?

СОРТИРОВКА ПОДСЧЕТОМ
Пусть у нас есть массив source из n десятичных цифр ( m = 10 ). Например, source[7] = { 7, 9, 8, 5, 4, 7, 7 }, n=7. Здесь положим const k=1.

Создать массив count из m элементов(счетчиков).
Присвоить count[i] количество элементов source, равных i. Для этого:
проинициализовать count[] нулями,
пройти по source от начала до конца, для каждого числа увеличивая элемент count с соответствующим номером.for( i=0; iПрисвоить count[i] значение, равное сумме всех элементов до данного: count[i] = count[0]+count[1]+...count[i-1]. В нашем примере count[] = { 0, 0, 0, 0, 1, 2, 2, 2, 5, 6 } Эта сумма является количеством чисел исходного массива, меньших i.
Произвести окончательную расстановку.

сколько чисел меньше него - это значение хранится в count[

source[i] ].
Таким образом, нам известно окончательное место числа в упорядоченном массиве: если есть K чисел меньше данного, то оно должно стоять на позиции K+1. 
Осуществляем проход по массиву source слева направо, одновременно заполняя выходной массив dest:
for ( i=0; i c = source[i];
dest[ count[c] ] = c;
count[c]++; // для повторяющихся чисел
}

Таким образом, число c=source[i] ставится на место count[c]. На этот случай, если числа повторяются в массиве, предусмотрен оператор count[c]++, который увеличивает значение позиции для следующего числа c, если таковое будет.
Циклы занимают (n + m) времени. Столько же требуется памяти.

m) сортировать цифры. А от цифр до строк и чисел

- 1 шаг. Пусть у нас в каждом ключе k цифр ( m = 10 ). Аналогично случаю со списками отсортируем их в несколько проходов от младшего разряда к старшему.








Общее количество операций, таким образом, ( k(n+m) ), при используемой дополнительно памяти (n+m). Эта схема допускает небольшую оптимизацию. Заметим, что сортировка по каждому байту состоит из 2 проходов по всему массиву: на первом шаге и на четвертом. Однако, можно создать сразу все массивы count[] (по одному на каждую позицию) за один проход. Неважно, как расположены числа - счетчики не меняются, поэтому это изменение корректно.
Таким образом, первый шаг будет выполняться один раз за всю сортировку, а значит, общее количество проходов изменится с 2k на k+1.

представление целых беззнаковых чисел. На хранение каждого из базовых типов

выделяется строго определенное количество байт. Как правило, распределение такое:

unsigned char - 1 байт,
unsigned short int - 2 байта,
unsigned long int - 4 байта.

При этом большинство процессоров использует обратный порядок записи: от младшего байта к старшему. Так число типа short int i = 669110 = 0x1A23 непосредственно в памяти хранится так:


Если это число имеет тип long int, то под него выделяется 4 байта: long int i = 669110 = 0x00001A23.


В конце расположены ведущие нули. Таким образом, необходимо провести сортировку от начала числа к концу. Каждый байт может принимать в общем случае 256 значений: m=256.

counters-массив для счетчиков, N-число элементов в data
template
void createCounters(T *data,

long *counters, long N) {
// i-й массив count расположен, начиная с адреса counters+256*i
memset( counters, 0, 256*sizeof(T)*sizeof(long) );

uchar *bp = (uchar*)data;
uchar *dataEnd = (uchar*)(data + N);
ushort i;

while ( bp != dataEnd ) {
// увеличиваем количество байт со значением *bp
// i - текущий массив счетчиков
for (i=0; i counters[256*i + *bp++]++;
}
}

качестве параметров
// номер байта Offset,
// число элементов N,
// исходный

массив source,
// массив dest, куда будут записываться числа, отсортированные по байту Offset
// массив счетчиков count, соответствующий текущему проходу.

template
void radixPass (short Offset, long N, T *source, T *dest, long *count) {
// временные переменные
T *sp;
long s, c, i, *cp;
uchar *bp;


// шаг 3
s = 0; // временная переменная, хранящая сумму на данный момент
cp = count;
for (i = 256; i > 0; --i, ++cp) {
c = *cp;
*cp = s;
s += c;
}

// шаг 4
bp = (uchar *)source + Offset;
sp = source;
for (i = N; i > 0; --i, bp += sizeof(T) , ++sp) {
cp = count + *bp;
dest[*cp] = *sp;
++(*cp);
}
}

sizeof(T) проходов по направлению от младшего байта к старшему.
// сортируется

массив in из N элементов
// T - любой беззнаковый целый тип
template
void radixSort (T* &in, long N) {
T *out = new T[N];
long *counters = new long[sizeof(T)*256], *count;
createCounters(in, counters, N);

for (ushort i=0; i count = counters + 256*i; // count - массив счетчиков для i-го //разряда

if ( count[0] == N ) continue; // (*** см ниже)

radixPass (i, N, in, out, count); // после каждого шага входной и
swap(in, out); // выходной массивы меняются местами
}
// по окончании проходов
delete out; // вся информация остается во входном массиве.
delete counters;
}
Обратим внимание, что если число проходов нечетное(например, T=unsigned char), то из-за перестановки swap() реально уничтожается исходный массив, а указатель in приобретает адрес out. Об этом следует помнить, используя указатели на сортируемый массив во внешней программе.
Такая организация процедуры также является прототипом для сортировки строк: достаточно сделать проходы radixPass от последней буквы к первой.
Строка, помеченная (***) представляет собой небольшую оптимизацию. Бывает так, что сортируемые типы используются не полностью. Например, в переменных ulong хранятся числа до 65536(=2562) или до 16777216(=2563). При этом остается еще один или два старших разряда, которые всегда равны нулю. В переменной count[0] хранится общее количество нулевых байтов на текущей сортируемой позиции, и если оно равно общему количеству чисел, то сортировка по этому разряду не нужна. Так radixSort сама адаптируется к реальному промежутку, в котором лежат числа.

с плавающей точкой
Эффективность поразрядной сортировки
Результаты тестирования

также, за исключением одной важной детали. А именно, если выписать

число в двоичном представлении, то первый бит старшего байта является знаковым.
Рассмотрим 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:
long numNeg=0; // количество отрицательных чисел
for(i=128;i<256;i++) numNeg += count[i];

На шаге 3 увеличиваем начальную позицию положительных чисел на numNeg, а отрицательные записываем с начала массива. Это приводит к следующей процедуре:
// проход поразрядной сортировки по старшим байтам,
// для целых чисел со знаком Offset = sizeof(T)-1.
template
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];

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

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 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, который используется в IBM PC, Macintosh, Dreamcast и ряде других систем. Зафиксировав формат представления числа, уже можно модифицировать соответствующим образом сортировку.

Любое число можно записать в системе с основанием BASE как M*BASEn, где |M|
Такая запись называется нормализованной. M называется мантиссой, n - порядком числа. Стандарт IEEE-754 предполагает запись числа в виде [знак][порядок][мантисса]. Различным форматам соответствует свой размер каждого из полей. Для чисел одинарной точности(float) это 1 бит под знак, 8 под порядок и 23 на мантиссу. Числа двойной точности(double) имеют порядок из 11 бит, мантиссу из 52 бит. Некоторые процессоры(например, 0x86) поддерживают расширенную точность(long double).

тип/бит [Знак] [Порядок] [Мантисса] [Смещение]
float 1 8 23 127
double 1 11 52 1023

значение знакового бита 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.

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

вместо единицы ноль с точкой. Так что формула меняется на

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(все единицы) зарезервировано под "нечисла".

одна интересная особенность. А именно, если значение поля [Порядок] у

одного числа больше соответствующего значения у другого, то первое число обязательно больше второго. Это следует непосредственно из формул перевода (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.

на массиве:   
-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
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
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 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}, в зависимости от входного типа данных.

по оценке, поразрядная сортировка растет линейным образом по n, так

как k,m - константы.
Также она растет линейным образом по k - при увеличении длины типа(количества разрядов) соответственно возрастает число проходов. Однако, в последний пункт реальные условия вносят свои коррективы.
  Дело в том, что основной цикл сортировки по i-му байту состоит в движении указателя uchar* bp шагами sizeof(T) по массиву для получения очередного разряда.

Когда T=char, шаг равен 1, T=short - шаг равен 2, T=long - шаг равен 4... Чем больше размер типа, тем менее последовательный доступ к памяти осуществляется, а это весьма существенно для скорости работы. Поэтому реальное время возрастает чуть быстрее, нежели теоретическое.

Кроме того, поразрядная сортировка уже по своей сути неинтересна для малых массивов. Каждый проход содержит минимум 256 итераций, поэтому при небольших n общее время выполнения (n+m) определяется константой m=256.

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

результаты сравнений поразрядной сортировки (синяя линия) и быстрой(розовая линия), причем

использовалась функция sort() из библиотеки STL.

short Благодаря малой разрядности и простоте внутренних циклов, поразрядная перегнала быструю сортировку уже на 100 элементах.
long При переходе к типу long произошло двукратное увеличение количества проходов RadixPass, поэтому худшая асимптотика быстрой сортировки показала себя лишь после 600 элементов, где она начала отставать.
float По графику видно, что для этого типа поразрядная сортировка оказалась гораздо эффективнее, нежели для long. В чем дело, ведь размер одинаков - 4 байта ? Оказывается, на типе float резко возрастает время работы быстрой сортировки. Возможно, это связано с тем, что процессор, прежде чем делать какие-либо операции, переводит его в double, а потом работает с этим типом, который 2 раза больше по размеру.. Так или иначе, быстрая сортировка стала работать в 2 раза медленнее, и поразрядная вышла вперед после 100 элементов.
double График показан с десятикратным увеличением. Размер типа увеличился в 2 раза, поэтому для небольших n поразрядная сортировка, конечно, отстает, но перегоняет быструю на массивах из нескольких тысяч элементов. Небольшое преимущество radixSort длится приблизительно до 16000 элементов, когда данные начинают вылезать за пределы кэша. Соответственно, начинает играть роль медленный непоследовательный доступ (с шагами по 8 байт) к основной памяти.. В результате поразрядная сортировка снова выбивается вперед лишь после 500000 элементов.