Поразрядная сортировка беззнаковых целых чисел

В качестве интересного примера рассмотрим компьютерное представление целых беззнаковых чисел. На хранение каждого из базовых типов выделяется строго определенное количество байт. Как правило, распределение такое:

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.

// Создать счетчики.// data-сортируемый массив, counters-массив для счетчиков, N-число элементов в datatemplate<class T>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<sizeof(T);i++) counters[256*i + *bp++]++; }} // Функция radixPass принимает в качестве параметров// номер байта Offset,// число элементов N, // исходный массив source, // массив dest, куда будут записываться числа, отсортированные по байту Offset// массив счетчиков count, соответствующий текущему проходу. template<class T>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<class T>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<sizeof(T); 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 сама адаптируется к реальному промежутку, в котором лежат числа.