Цифровая поразрядная сортировка

Цифровая поразрядная сортировка рассматривает ключ как последовательность цифр в некоторой системе счисления с основанием P. Подсчитаем, сколько имеется в таблице ключей с младшей цифрой d (d=0…P-1). Для этого потребуется Pсчетчиков С₀, С₁,… С_P-1 и дополнительная область памяти для вывода в нее записей или указателей на записи. После подсчета ясно, что все ключи с младшей цифрой 0 должны размещаться с позиции 0, ключи с цифрой 1 – с позиции С₀, с цифрой 2 – с позиции С₀+С₁ и так далее. Затем та же самая процедура выполняется для последующих цифр. Рис. 38 поясняет процесс сортировки.

Рис.38 Цифровая поразрядная сортировка

Сравнение ключей не производится. Фактически каждый просмотр состоит из 3-х фаз – подсчет, распределение памяти, перемещение. Две из них можно совместить – накапливать значения счетчиков для k+1 просмотра одновременно с перемещением k-го просмотра. В качестве системы счисления естественно выбрать 16-ричную (байт ключа содержит 2 цифры) или систему счисления с основанием 256 (1 байт ключа – 1 цифра). Поскольку алгоритм допускает рас­па­раллеливание, он весьма эффективен для много­процессорных компьютеров. Ниже приведен текст функции, реализующей метод.

const int NDIGIT=256; // основание системы счисления

//----------------------------------------------

void DigitalSort(BYTE *t, int N, int KeyLen){

// цифровая поразрядная сортировка

// (основание системы счисления=256)

// t - сортируемый массив ключей

// N - число ключей в массиве

// KeyLen - число цифр в сортируемом ключе

int *Count;