Двоичная поразрядная сортировка

Алгоритм рассматривает ключи как последовательности битов. Таблица сортируется сначала по старшему значащему биту так, чтобы все ключи со старшим битом ‘0’ предшествовали ключам со старшим битом ‘1’. Затем та же процедура выполняется для второго бита и полученных двух частей таблицы.

int BitPart(unsigned int Left, unsigned int Right,

unsigned int Tab[], unsigned int Bit){

// разделение отрезка таблицы Tab от Left до Right

// по биту Bit

int i,j,k;

bool l,r; // l=true, если бит Bit в ключе = 1

// r=true, если бит Bit в ключе = 0

unsigned int x;

i=Left;

j=Right;

k=-1;

while(j>=i){

// перемещая i слева направо, находим ключ с битом Bit = 1

// перемещая j справа налево, находим ключ с битом Bit = 0

l=((Tab[i] & Bit) != 0); // l=true, если бит Bit в ключе = 1

r=((Tab[j] & Bit) == 0); // r=true, если бит Bit в ключе = 0

if(!l) k=i++;

if(!r) j--;

if(l && r ){

// бит в ключе слева равен 1

// бит в ключе справа равен 0

// меняем их местами

x=Tab[i]; Tab[i]=Tab[j]; Tab[j]=x;

k=i; // k - индекс самого правого ключа с битом 0

i++;

j--;

}

}

if(i>Right){

return Right;

} else {

if(j<Left){

return Left-1;

} else {

return k;

}

}

}

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

void BitSort(unsigned int Left, unsigned int Right,

unsigned int Tab[],unsigned int Bit){

// сортировка таблицы Tab на отрезке Left - Right

// по битам, начиная с бита Bit

int k;

if(Left>=Right) return;

k=BitPart(Left,Right,Tab,Bit);

if((Bit>>1)!=0){

BitSort(Left,k,Tab,Bit>>1);

BitSort(k+1,Right,Tab,Bit>>1);

}

}

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

void BinarySort(int n,unsigned Tab[], unsigned int keylen){

// прокладка к BitSort, чтобы не пугать пользователя

// аргументами BitSort

unsigned Bit;

Bit=(1<<(keylen-1));

BitSort(0,n-1,Tab,Bit);

}

Рассмотренная сортировка так же, как и следующая, не основана на сравнении ключей. Приблизительную оценку времени работы можно получить из следующих соображений. Пусть длина ключа М битов. Если таблица содержит все возможные ключи, которые можно составить из М битов, то число ключей или . Таким образом, для сортировки нужно пройти все данные столько раз, сколько битов в ключе и время работы пропорционально .