Естественное (Неймановское) слияние.

Previous  Top  Next

    
 

Естественное (Неймановское) слияние.

 

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

 

Записи, идущие в порядке неубывания ключей, сцепляются, образуя подсписок. Минимальный подсписок одна запись.

 

Пример:

 

Пусть даны ключи записей

 

5    7    8    3    9     4    1    7    6

 

Ищем подсписки

 

В один общий список соединяются 1-й, 3-й, 5-й и т. д. подсписки, в другой - 2-й, 4-й и т. д. подсписки.

 

Произведем слияние 1 подсписка 1 списка и 1 подсписка 2 списка, 2 подсписка 1 списка и 2 подсписка 2 списка и т.д.

 

Будут получены следующие цепи

 

3 --> 5 --> 7 --> 8 --> 9 и 1 --> 4 --> 7

 

Подсписок, состоящий из записи "6", пары не имеет и "принудительно" объединяется с последней цепью, принимающей вид 1 --> 4--> 6 --> 7.

 

При нашем небольшом числе записей 2-й этап, на котором сливаются две цепи, окажется последним.

 

В общем случае на каждом этапе подсписок - результат слияния начальных подсписков 1 и 2 списка становится началом нового 1-го списка, а результат слияния следующих двух подсписков - началом 2-го списка. Следующие образуемые подсписки поочередно включаются в 1-й и во 2-й список.

 

Для программной реализации заводят массив sp: элемент sp[i] - это номер записи, которая следует за i-й.

 

Последняя запись одного подсписка ссылается на первую запись другого, а для различения концов подсписков эта ссылка снабжается знаком минус.

Code:

Repeat {Повторение актов слияний подсписков}

If A[j].kl < A[i].kl Then {Выбирается меньшая запись}

Begin sp[k]:=j; k:=j; j:=sp[j];

If j<=0 Then {Сцепление с остатком "i"-подсписка}

Begin sp[k]:=i; Repeat m:=i; i:=sp[i] Until i<=0 End

End

Else

Begin sp[k]:=i; k:=i; i:=sp[i];

If i<=0 Then {Сцепление с остатком "j"-подсписка}

Begin sp[k]:=j; Repeat m:=j; j:=sp[j] Until j<=0 End

End;

If j<=0 Then Begin sp[m]:= 0; sp[p]:=-sp[p]; i:=-i;

j:=-j; If j<>0 Then p:=r; k:=r; r:=m End

Until j=0;

 

 

 

 

 

 

 

 

 

{В конец сформированного подсписка всегда заносится нулевая ссылка (sp[m]:= 0), ибо он может оказаться последним.

 

Действие sp[p]:= -sp[p] обозначает минусом конец ранее построенного подсписка.

 

В переменных i,j ссылки на начала новых сливаемых подсписков - со знаком минус; его снимаем. Переход к новым подспискам требует обновления переменных p, k, r}

Автор: www.structur.h1.ru

©Drkb::04171

http://delphiworld.narod.ru/

DelphiWorld 6.0