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

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

Последним алгоритмом, который мы рассмотрим в этой главе, снова будет сортировка слиянием, но в этот раз применительно к связным спискам. Как вы, наверное, помните, несмотря на высокие показатели быстродействия (алгоритм класса 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;

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

И последняя часть реализации сортировки - сама функция слияния. Ее код приведен в листинге 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. Сортировка слиянием для двухсвязного списка

function TtdDoubleLinkList.dllMerge(aCompare : TtdCompareFunc;

aPriorNode1: PdlNode;

aCount1 : longint;

aPriorNode2: PdlNode;

aCount2 : longint);

PdlNode;

var

i : integer;

Node1 : PdlNode;

Node2 : PdlNode;

LastNode : PdlNode;

Temp : PdlNode;

begin

LastNode := aPriorNode1;

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

Node1 := aPriorNode1^.dlnNext;

Node2 := aPriorNode2^.dlnNext;

{повторять до тех nop, пока один из списков не опустеет}

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

begin

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

LastNode := Node1;

Node1 := Node1^.dlnNext;

dec(aCount1);

end

else begin

Temp := Node2^.dlnNext;

Node2^.dlnNext := Node1;

LastNode^.dlnNext := Node2;

LastNode := Node2;

Node2 := Temp;

dec(aCount2);

end;

end;

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

if (aCount1 = 0) then begin

LastNode^.dlnNext := Node2;

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

end

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

else begin

for i := 0 to pred(aCount1) do LastNode := LastNode^.dlnNext;

LastNode^.dlnNext := Node2;

end;

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

Result := LastNode;

end;

function TtdDoubleLinkList.dllMergesort(aCompare : TtdCompareFunc;

aPriorNode : PdlNode; aCount : longint): PdlNode;

var

Count2 : longint;

PriorNode2 : PdlNode;

begin

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

if (aCount = 1) then begin

Result := aPriorNode^.dlnNext;

Exit;

end;

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

Count2 := aCount div 2;

aCount := aCount - Count2;

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

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

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

dllMergeSort(aCompare, PriorNode2, Count2);

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

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

end;

procedure TtdDoubleLinkList.Sort(aCompare : TtdCompareFunc);

var

Dad, Walker : PdlNode;

begin

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

if (Count > 1) then begin

dllMergesort(aCompare, FHead, Count);

Dad := FHead;

Walker := FHead^.dlnNext;

while (Walker <> nil) do

begin

Walker^.dlnPrior := Dad;

Dad := Walker;

Walker := Dad^.dlnNext;

end;

end;

MoveBeforeFirst;

FIsSorted := true;

end;

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

2.4. Создание списков

Из книги автора

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


Параметры списков

Из книги автора

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


Параметры списков

Из книги автора

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


1.13. Оформление списков

Из книги автора

1.13. Оформление списков При оформлении маркированного списка наиболее предпочтительно использовать символ. Знак маркировки должен находиться в начале абзаца. Расстояние от левого края печати до текста в списке должно составлять 0,63 см (что соответствует стандартным


7.5. Обработка списков

Из книги автора

7.5. Обработка списков В этом разделе мы рассмотрим некоторые основные предикаты, полезные при работе со списками. Поскольку Пролог позволяет работать с произвольными структурами данных, списки не могут играть в нем той незаменимой роли, какая им отводится в других языках


Достоинства и недостатки связных списков

Из книги автора

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


Пример 24-3. Комбинирование "ИЛИ-списков" и "И-списков"

Из книги автора

Пример 24-3. Комбинирование "ИЛИ-списков" и "И-списков" #!/bin/bash# delete.sh, утилита удаления файлов.# Порядок использования: delete имя_файлаE_BADARGS=65if [ -z "$1" ]then echo "Порядок использования: `basename $0` имя_файла" exit $E_BADARGS # Если не задано имя файла.else file=$1 # Запомнить имя файла.fi[ ! -f "$file" ]


3.1. Представление списков

Из книги автора

3.1. Представление списков Список — это простая структура данных, широко используемая в нечисловом программировании. Список — это последовательность, составленная из произвольного числа элементов, например энн, теннис, том, лыжи. На Прологе это записывается так:[ энн,


6.2.2. Вывод списков

Из книги автора

6.2.2. Вывод списков Кроме стандартного прологовского формата для списков существуют несколько других естественных форм их внешнего представления, которые в некоторых ситуациях являются более предпочтительными. Следующая процедуравывспис( L)выводит список L так, что


9.1. Представление списков. Сортировка

Из книги автора

9.1. Представление списков. Сортировка 9.1.1. Замечания в некоторых альтернативных способах представления списков В главе 3 была введена специальная система обозначений для списков (специальная прологовская нотация), которую мы и использовали в последующем изложении.


9.1.2. Сортировка списков

Из книги автора

9.1.2. Сортировка списков Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядкабольше( X, Y)означающее, что X больше, чем Y,


1.13. Оформление списков

Из книги автора

1.13. Оформление списков При оформлении маркированного списка наиболее предпочтительно использовать символ «». Знак маркировки должен находиться в начале абзаца. Расстояние от левого края печати до текста в списке должно составлять 0,63 см (что соответствует стандартным


Сортировка списков данных

Из книги автора

Сортировка списков данных Нередко возникает необходимость отсортировать данные в списке, то есть упорядочить записи по значению определенного поля. В Excel 2007 для сортировки данных имеются команды на двух вкладках ленты:? в группе Редактирование вкладки Главная есть