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

Алгоритм рассматривает ключи как последовательности битов. Таблица сортируется сначала по старшему значащему биту так, чтобы все ключи со старшим битом ‘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