Цифровая поразрядная сортировка
Цифровая поразрядная сортировка рассматривает ключ как последовательность цифр в некоторой системе счисления с основанием P. Подсчитаем, сколько имеется в таблице ключей с младшей цифрой d (d=0…P-1). Для этого потребуется Pсчетчиков С0, С1,… СP-1 и дополнительная область памяти для вывода в нее записей или указателей на записи. После подсчета ясно, что все ключи с младшей цифрой 0 должны размещаться с позиции 0, ключи с цифрой 1 – с позиции С0, с цифрой 2 – с позиции С0+С1 и так далее. Затем та же самая процедура выполняется для последующих цифр. Рис. 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;
int i,j,k;
BYTE Dig;
BYTE *b; // буферная область
int *Pos; // позиции расстановки
Count=new int[NDIGIT]; // память для счетчиков
Pos=new int[NDIGIT]; // текущие позиции при расстановке
b=new BYTE [N*KeyLen]; // буферная область
for(i=0; i<KeyLen; i++){
for(k=0; k<NDIGIT; k++)Count[k]=0; // обнулим счетчики
// подсчет
for(j=0; j<N; j++){
// Dig - i-я цифра в j-м ключе
Dig=*(t+j*KeyLen+KeyLen-i-1);
Count[Dig]++;
}
// расчет позиций
Pos[0]=0;
for(j=1; j<NDIGIT; j++){
Pos[j]=Pos[j-1]+Count[j-1];
}
// расстановка
for(j=0; j<N; j++){
Dig=*(t+j*KeyLen+KeyLen-i-1);
memcpy(b+KeyLen*Pos[Dig]++, t+j*KeyLen, KeyLen);
}
// копируем то, что получилось в исходную область
// хотя можно было бы перекачивать туда-обратно
memcpy(t,b,KeyLen*N);
}
delete [] b;
delete [] Count;
delete [] Pos;
}