Фундаментальные алгоритмы и структуры данных в Delphi

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

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

Во-первых, потребуется написать метод-драйвер сортировки слиянием. Он будет просто вызывать рекурсивный метод, который и будет заниматься собственно сортировкой. Методу-драйверу будут передаваться два параметра: узел, с которого начинается сортируемый список, и количество элементов в списке. Мы не будем использовать nil в качестве сигнализатора окончания списка - для этого будет применяться счетчик узлов. Реализация простого метода-драйвера приведена в листинге 5.19.

Листинг 5.19. Метод-драйвер для сортировки слиянием односвязных списков

procedure TtdSingleLinkList.Sort(aCompare : TtdCompareFunc);

begin

{если в списке более одного элемента, выполнить сортировку слиянием}

if (Count > 1) then

sllMergesort(aCompare, FHead, Count);

MoveBeforeFirst;

FIsSorted := true;

end;

Как видите, для выполнения сортировки метод-драйвер вызывает функцию sllMergeSort. Эта функция сначала вызывает сама себя для первой, а затем - для второй половины списка, после чего обе половины объединяются в один список. Для обеспечения слияния функция sllMergeSort возвращает последний отсортированный узел.

Листинг 5.20. Рекурсивная сортировка слиянием для односвязных списков

function TtdSingleLinkList.sllMergesort(aCompare : TtdCompareFunc;

aPriorNode : PslNode;

aCount : longint): PslNode;

var

Count2 : longint;

PriorNode2 : PslNode;

begin

{сначала обрабатывается простой случай: если в списке всего один элемент, он отсортирован, поэтому выполнение функции завершается}

if (aCount = 1) then begin

Result := aPriorNode^.slnNext;

Exit;

end;

{разбить список на две части}

Count2 := aCount div 2;

aCount := aCount - Count2;

{выполнить сортировку слиянием первой половины: вернуть начальный узел для второй половины}

PriorNode2 := sllMergeSort(aCompare, aPriorNode, aCount);

{выполнить сортировку слиянием второй половины}

sllMergeSort(aCompare, PriorNode2, Count2);

{объединить две половины}

Result := sllMerge(aCompare, aPriorNode, aCount, PriorNode2, Count2);

end;

Метод сортировки слиянием вызывается с указанием начального узла сортируемого списка и количества узлов в списке. Имея такие входные данные, за счет прохождения списка и подсчета узлов можно определить, где начинается вторая половина списка. В качестве возвращаемого параметра после сортировки первой половины списка используется последний узел первой половины, который служит фиктивным начальным узлом для второй половины. В любом случае нам приходится проходить список. Тогда почему бы нам заодно не определить положение средней точки?

И последняя часть реализации сортировки - сама функция слияния. Ее код приведен в листинге 5.21. Она не представляет никаких трудностей для понимания. Начальным узлом объединенного списка будет служить родительский узел первого подсписка. Функция возвращает последний элемент объединенного списка (он будет использоваться в качестве родительского узла для несортированной части подсписка).

Листинг 5.21. Фаза слияния при сортировке слиянием односвязного списка

function TtdSingleLinkList.sllMerge( aCompare : TtdCompareFunc;

aPriorNode1 : PslNode; aCount1 : longint;

aPriorNode2 : PslNode; aCount2 : longint): PslNode;

var

i : integer;

Node1 : PslNode;

Node2 : PslNode;

LastNode : PslNode;

Temp : PslNode;

begin

LastNode := aPriorNode1;

{извлечь первые два узла}

Node1 := aPriorNode1^.slnNext;

Node2 := aPriorNode2^.slnNext;

{повторять цикл до исчерпания элементов одного из списков}

while (aCount1 <> 0) and (aCount2<> 0) do

begin

if (aCompare(Node1^.slnData, Node2^.slnData) <= 0) then begin

LastNode := Node1;

Node1 := Node1^.slnNext;

dec(aCount1);

end

else begin

Temp := Node2^.slnNext;

Node2^.slnNext := Node1;

LastNode^.slnNext := Node2;

LastNode := Node2;

Node2 := Temp;

dec(aCount2);

end;

end;

{если закончились элементы в первом списке, связать последний узел с оставшейся частью второго списка и пройти список до последнего узла}

if (aCount1 = 0) then begin

LastNode^.slnNext := Node2;

for i := 0 to pred(aCount2) do LastNode := LastNode^.slnNext;

end

{если закончились элементы во втором списке, то Node2 будет первым узлом в оставшемся списке; пройти список до последнего узла и связать его с узлом Node2}

else begin

for i := 0 to pred(aCount1) do

LastNode := LastNode^.slnNext;

LastNode^.slnNext := Node2;

end;

{вернуть последний узел}

Result := LastNode;

end;

Обратите внимание, что в односвязном списке сортировка слиянием не требует выполнения обратного прохода. Мы не были в ситуации, когда требовалось знание родительского узла определенного узла, а он не был известен. Это означает, что сортировка слиянием в двухсвязном списке может выполняться точно так же, как и в односвязном, но после сортировки нужно будет пройти весь список и восстановить обратные ссылки.

Листинг 5.22. Сортировка слиянием для двухсвязного списка