Информатика и технология программирования


Поразрядная сортировка разделением - часть 2


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


void mainsort(int B[], int n)
{
int max,i;
unsigned m;
for(max = 0, i=0; i&#60 n; i++)
if (B[i] &#62 max) max = B[i];
for (m=1; m &#60 max; m &#60&#60= 1);
m &#62&#62=1;
bitsort(B,0,n-1,m);
}

Для разделения интервала массива по заданному биту происходит по принципу "сжигания свечи с двух концов". Два индекса (i и j) движутся от концов интервала к середине, оставляя после себя слева и справа разделенные элементы. На каждом шаге производится сравнение битов по маске m в элементах массива, находящихся по указанным индексам (граница неразделенной части массива). В зависимости от комбинации битов (4 варианта) производится перестановка элементов и перемещение одного или обоих индексов к середине:


СОСТОЯНИЕ ПАРЫ ЭЛЕМЕНТОВ СДВИГ ГРАНИЦ
Оба на месте 0 1 Сдвинуть обе
Размещены наоборот 1 0 Переставить элементы, сдвинуть обе
Левый на месте 0 0 Сдвинуть левую
Правый на месте 1 1 Сдвинуть правую


{
int j,vv; // Цикл разделения массива
for (i=a, j=b; i&#60j; ) // в поразрядной сортировке
if ((A[i] &#38 m) ==0)
{
if ((A[j] &#38 m) !=0) i++,j--; // Вариант 0,1
else i++; // Вариант 0,0
}
else
{
if ((A[j] &#38 m) !=0) j--; // Вариант 1,1
else // Вариант 1,0
{
vv = A[i]; A[i]=A[j]; A[i]=vv;
i++, j--;
}
}
if ((A[i] &#38 m)!=0) i--; // Уточнить границу разделения




Начало  Назад  Вперед



Книжный магазин