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

Представьте себе, что имеется два уже отсортированных списка и необходимо сформировать один список, объединяющий все элементы исходных списков. План А состоит в том, чтобы скопировать оба списка в результирующий и выполнить его сортировку. Но в этом случае, к сожалению, мы не пользуемся тем, что исходные списки уже отсортированы. План Б предусматривает слияние. Смотрим на первые элементы в обоих списках. Элемент с меньшим значением переносим в результирующий список. Снова смотрим на первые элементы в обоих списках и снова переносим в результирующий список элемент с меньшим значением, удаляя его из исходного списка. Описанный процесс продолжается до тех пор, пока не исчерпаются элементы одного из списков. После этого в результирующий список можно перенести все оставшиеся в исходном списке элементы. Такой алгоритм формально известен под названием алгоритма двухпутевого слияния (two-way merge algorithm ).

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

Листинг 5.11. Слияние двух отсортированных массивов TList

procedure TDListMerge( aList 1, aList2, aTarget List : TList;

aCompare : TtdCompareFunc);

var

Inx1, Inx2, Inx3 : integer;

begin

{подготовить результирующий список}

aTargetList.Clear;

aTargetList.Capacity := aList1.Count + aList2.Count;

{инициализировать счетчики}

Inx1 := 0;

Inx2 := 0;

Inx3 := 0;

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

while (Inx1 < aList1.Count) and (Inx2 < aList2.Count) do

begin

{определить наименьшее значение из двух списков и скопировать его в результирующий список; увеличить значения индексов на единицу}

if aCompare (aList1.List^[Inx1], aList2.List^[Inx]) < = 0 then begin

aTargetList.List^[Inx3] := aList1.List^[Inx1];

inc(Inx1);

end

else begin

aTargetList.List^[Inx3] := aList2.List^[Inx2];

inc(Inx2);

end;

inc(Inx3);

end;

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

if (Inx1 < aList1.Count) then

Move(aList1.List^[Inx1], aTargetList.List^[Inx3],

(aList1.Count - Inx1) * sizeof(pointer)) {в противном случае скопировать все элементы, оставшиеся во втором списке, в результирующий список}

else

Move(aList2.List^[Inx2], aTargetList.List^[Inx3], (aList2.Count - Inx2) * sizeof(pointer));

end;

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

Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих исходных списках. Если в первом из них находится n элементов, а во втором - m, нетрудно прийти к выводу, что в худшем случае будет произведено (n + m) сравнений. Следовательно, алгоритм двухпутевого слияния принадлежит к классу O(n).

Каким же образом алгоритм двухпутевого слияния помогает выполнить сортировку? Для его работы необходимо иметь два отсортированных списка меньшей длины, из которых создается один больший список. На основе такого описания можно прийти к рекурсивному определению сортировки слиянием: разделите исходный список на две половины, примените к каждой половине алгоритм сортировки слиянием, а затем с помощью алгоритма слияния объедините подсписки в один отсортированный список. Рекурсия заканчивается, когда под-под-подсписок, переданный алгоритму сортировки, содержит всего один элемент, поскольку он, очевидно, является отсортированным.

Сортировка слиянием обладает только одним недостатком - алгоритм слияния требует наличия третьего списка, в котором будут храниться результаты слияния.

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