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

Цифровая поразрядная сортировка рассматривает ключ как последовательность цифр в некоторой системе счисления с основанием 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;

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;

}

Дата добавления: 2014-12-08