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

Сортировка слиянием для связных списков

Последним алгоритмом, который мы рассмотрим в этой главе, снова будет сортировка слиянием, но в этот раз применительно к связным спискам. Как вы, наверное, помните, несмотря на высокие показатели быстродействия (алгоритм класса O(n log(n))), использование сортировки слиянием требует наличия вспомогательного массива, размер которого составляет половину размера сортируемого массива. Такая необходимость вызвана тем, что на этапе слияния сортировке нужно куда-то помещать элементы.

Для связных списков сортировка слиянием не требует наличия вспомогательного массива, поскольку элементы можно свободно перемещать, разрывая и восстанавливая связи, с быстродействием O(1), т.е. за постоянное время.

Код для сортировки связных списков можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnkLst.pas.

Давайте рассмотрим, каким образом работает код для односвязных списков, а затем расширим концепцию для двухсвязных списков.

Предположим, что имеется связный список с фиктивным начальным узлом. (С учетом этого предположения алгоритм сортировки намного упрощается.) Таким образом, каждый сортируемый нами узел будет иметь родительский узел. Рассмотрим процесс слияния. Пусть имеются два списка, описываемых родительскими узлами первых узлов. Будем считать, что оба списка отсортированы. Можно легко разработать алгоритм слияния с целью объединения двух списков в один. При этом процесс слияния будет заключаться в выполнении удалений и вставок.

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

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

Во-первых, потребуется написать метод-драйвер сортировки слиянием. Он будет просто вызывать рекурсивный метод, который и будет заниматься собственно сортировкой. Методу-драйверу будут передаваться два параметра: узел, с которого начинается сортируемый список, и количество элементов в списке. Мы не будем использовать 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;