Первая версия программы сортировки с помощью простого слияния имеет следующий вид

	int i,	j,	k, 1;
	int up	, p;
	up=l;
	p=l;
/*	индексация	индексов	*/
	do
	{
	if	(up=	= 1)
	{	i=l;

j=n;

k=n+l;

l=2*n;

} else

{

k=l; l=n; i=n+l; j=2*n;

} /* слияние р-наборов из i- и j-входов в к- и 1-выходы */

up=-up;

р=2*р;

}

while(p==n);

Уточним действия, описанные на естественном языке. Ясно, что процесс слияния п элементов сам представляет собой последовательность слияний последовательностей, т. е. /^-наборов. После каждого такого частичного слияния выход переключается с нижнего на верхний конец выходного массива и наоборот, что гарантирует одинаковое распределение в обоих направлениях. Если сливаемые элементы направляются в левый конец выходного массива, то направление задается индексом к, и после пересылки очередного элемента он увеличивается на единицу. Если же элементы направляются в правый конец, то направление задается индексом / и он каждый раз уменьшается. Для упрощения фактического оператора слияния будем считать, что направление всегда задается индексом к, но после слияния /^-набора будем менять местами значения к и /, приращение же всегда обозначается через h, имеющее значение либо 1, либо -1. Высказанные соображения приводят к такому уточнению программы.

h=l;
m=n;
/*m — число	сливаемых элементов*/
do
{
q=p;
r=p;
m=m-2*p;

/^слияние q-элементов из i-входа с г элементами из j-входа; индекс выхода к, затем к увеличиваем на h*/

h=-h; /*обмен значениями к и 1*/

}

while(m==0);

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

while {

((q!=0) && (r!=0))

if (a[i]<a[j])

{ /* элемент из i-входа пересылается на k-выход; ink продвигаются*/

q=q-l;

}

else

{ /* элемент из j-входа посылается на k-выход; j и к продвигаются*/

г=г-1;

} }

/^копирование хвоста i-массива; копирование хвоста j-массива;*/

Если теперь уточнить операции копирования остатков, то программа станет совершенно точной. Однако, прежде чем сделать это, мы хотим избавиться от ограничения на п: пока оно должно быть степенью двойки. На какие части алгоритма влияло это условие? Легко убедить себя, что наилучший способ справиться с более общей ситуацией продолжать действовать, насколько это возможно, по-старому. В данной ситуации это означает, что мы будем продолжать слияние /^-наборов до тех пор, пока не останутся последовательности размером менее р. Этот процесс затрагивает только ту

часть, где определяются значения q и г — длины сливаемых последовательностей. Вместо трех операторов

q=p; г=р; т=т - 2*р; используется следующая конструкция:

iflm >=p)

q=p; else

q = m; т=т - q; if(m >=p)

r=p; else

r = m; m=m - r;. Здесь m — общее число элементов в двух входных последовательностях. Кроме того, для гарантии окончания программы условие р = 0, управляющее внешним циклом, заменяется на р>=п. Проделав все эти модификации, мы получаем следующую программу.

int i, j, k, 1, t;
int h, m, p, q, r;
int up;
/*У массива а индексы 1,	..,2*n.*/
up=l;
p=l;
do
{
h=l;
m=n;
if (up==l)
{
i=l;
j=n;
k=n+l;
l=2*n;
}
else
{
k=l;

l=n; i=n+l; j=2*n; }

do {

/* слияние серий из i и j в к-

выход*/

/* q — длина серии из i, r — длина

серии из j */

if (m>=p)

q=p; else

q=m; m=m-q;

if (1>=P)

r=p; else

r=m; m=m-r;

while(q!=0 && r!=0)

{ /* слияние */

if (a[i]<a[j])

{

a[k]=a [i];

k=k+h;

i=i+l;

q=q-l; } else

{

a[k]=a[j]; k=k+h;

j=j-i;

r=r-l; } }

/* копирование остатка серии из j*/

while(r!=0) { а[к]=a[j]; k=k+h;
j=j-i; r=r-l; }
/* копирование остатка	серии из i*/
while(q!=0) { a[k]=a [i]; k=k+h; i=i+l;
q=q-l; }
h=-h; t=k; k=l; l=t;
} while(m==0);
up=-up; p=2*p;
} while(p>=n);
if (up==0) { for(i=l; i<n; i++) a[i]=a[i+n]; }

Анализ алгоритма. Поскольку на каждом проходе р удваивается и сортировка заканчивается при р >= п, то всего требуется log n проходов. На каждом проходе по определению копируются по одному разу все п элементов. Поэтому общее число пересылок

М = n-\ogn.

Число сравнений ключей С даже меньше М, поскольку при копировании остатков никаких сравнений не производится. Однако, поскольку сортировки слиянием обычно употребляются в ситуациях, где приходится пользоваться внешними запоминающими устройствами, то затраты на операции пересылки на несколько порядков превышают затраты на сравнения. Поэтому детальный анализ числа сравнений особого практического интереса не представляет.

Алгоритм сортировки слиянием выдерживает сравнение даже с усовершенствованными методами сортировки. Однако, хотя здесь относительно высоки затраты на работу с индексами, решающее значение играет необходимость работать с памятью размером 2п. Поэтому сортировка слиянием для массивов, т. е. для данных, размещаемых в оперативной памяти, используется редко.

Дата добавления: 2014-11-29