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


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


{
int step,m,k0;
for (m=n; m!=1; m/=2) // Проверка на степень 2


if (m%2 !=0) return;
for (step=1 step &#60n; step *=2) // Слияние группами по


{ // step = 1,2,4...n/2


for (k0=0; k0 &#60 n/2; k0 += step)
// Распределить in[], начиная с 2*k0, группy по step


// элементов в v1 и в v2, начиная с k0


for (k0=0; k0 &#60 n; k0 += step*2)
// "Слить" по step элементов из v1 и v2, начиная с k0,


// в in[], начиная с 2*k0


}
}

Часть алгоритма, которая распределяет, начиная с 2*k0 из массива in группу из step элементов в массив v1 и такую же группу в v2, в комментариях не нуждается:


int i;
for (i=0, i&#60step; i++) v1[k0 + i] = in[2*k0 + i];
for (i=0, i&#60step; i++) v2[k0 + i] = in[2*k0 + step + i];

Часть алгоритма, выполняющего слияние, не так очевидна. В ней используются относительные индексы i1 и i2, которые последовательно " отсчитывают " элементы в группах из v1 и v2. Процесс продолжается, пока обе группы не будут "слиты". Первоначально проверяется факт окончания каждой из групп, тогда элемент берется из противоположной. В противном случае выбирается меньший элемент из двух текущих в группах:


int i1,i2;
for (i1=i2=0; i1+i2 &#60 2*step; )
{
if (i1==step)
{ in[2*k0+i1+i2] = v2[k0+i2]; i2++; }
else
if (i2==step)
{ in[2*k0+i1+i2] = v1[k0+i1]; i1++; }
else
if (v1[k0+i1] &#60 v2[k0+i2])
{ in[2*k0+i1+i2] = v1[k0+i1]; i1++; }
else
{ in[2*k0+i1+i2] = v2[k0+i2]; i2++; }
}

Некоторая сложность алгоритма простого слияния состоит в слежении за группами, в результате чего получаются такие " дикие " индексы массивов. ПОРАЗРЯДНАЯ РАСПРЕДЕЛЯЮЩАЯ СОРТИРОВКА работает с двумя последовательностями целиком, не выделяя в нем групп. Слияние осуществляется как обычно, путем выбора минимального из двух текущих элементов последовательностей. Зато распределение происходит на первом шаге по значению старшего значащего бита (0/1), и по значению каждого следующего бита на очередном шаге. Алгоритм при этом упрощается настолько, что приведен в "Вопросах без ответов...".Распределение можно вести одновременно для нескольких соседних битов, при этом количество выходных массивов будет равно соответствующей степени 2.




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



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