Обменная поразрядная сортировка

Массив сортируется по старшему значащему двоичному биту таким образом, что все элементы, начинающиеся с 0, окажутся слева, а начинающиеся с 1 – справа. Для того чтобы выполнялось это условие, находим самый левый элемент x [ i ] , начинающийся с 1, и самый правый x [ j ] , начинающийся с 0. Затем эти элементы меняем местами. Процесс повторяется, пока i < j .

Пуст F 0 – массив элементов, начинающихся с 0, F 1 – с 1. Применим поразрядную сортировку по следующему биту рекурсивно к F 0 и F 1 .

Для реализации этого алгоритма разработаем рекурсивную функцию, аргументами которой являются левый и правый индексы сортируемых элементов массива, массив и номер бита, по которому сортируется массив:

void bsort (int l, int u, int *x, int b)

{

if (b<0) return;

if (l>=u) return;

i=l; j=u;

while (i<j)

{ while (i<j && bit(x[i],b)==0) i++;

while (i<j && bit(x[j],b)==1) j--;

if (i<j) swap (&x[i], &x[j]);

}

if (bit(x[i],b)==1) i--;

bsort (0, i, x, b-1); bsort (i+1, n-1, x, b-1);

}

Здесь функция int bit ( a , b ) возвращает 1 если число a содержит бит с номером b , и 0 – в противном случае. Она может состоять из одного оператора if  ( a &(1<< b ))  return 1;  else   return  0;

Окончательный текст программы и вызывающей подпрограммы:

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

#include <conio.h>

void swap (int *a, int *b)

{

int temp=*a; *a=*b; *b=temp;

}

int bit (int a, int b)

{

if (a&(1<<b)) return 1;

else return 0;

}

void bsort (int l, int u, int *x, int b)

{

int i,j;

if (b<0 || b>15) return;

if (l>=u) return;

i=l; j=u;

while (i<j)

{ while (i<j && bit(x[i],b)==0) i++;

while (i<j && bit(x[j],b)!=0) j--;

if (i<j) swap (&x[i], &x[j]);

}

while (bit(x[i],b)!=0) i--;

bsort (l, i, x, b-1); bsort (i+1, u, x, b-1);

}

main()

{

int i, a[10];

clrscr();

randomize();

for (i=0; i<10; i++) a[i]=random(3000);

printf(" До сортировки :\n");

for (i=0; i<10; i++) printf (" %d ", a[i]);

bsort (0, 9, a, 15);

printf("\n После сортировки :\n");

for (i=0; i<10; i++) printf (" %d ", a[i]);

// i=16;

// if (bit(i, 3)) printf("\n 8 bit 3");

getch ();

}

Результаты работы программы

До сортировки:

66 1459 1697 2053 737 544 2618 1385 1531 2334

После сортировки:

66 544 737 1385 1459 1531 1697 2053 2334 2618