Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих исходных списках. Если в первом из них находится n элементов, а во втором - m, нетрудно прийти к выводу, что в худшем случае будет произведено (n + m) сравнений. Следовательно, алгоритм двухпутевого слияния принадлежит к классу O(n).
Каким же образом алгоритм двухпутевого слияния помогает выполнить сортировку? Для его работы необходимо иметь два отсортированных списка меньшей длины, из которых создается один больший список. На основе такого описания можно прийти к рекурсивному определению сортировки слиянием: разделите исходный список на две половины, примените к каждой половине алгоритм сортировки слиянием, а затем с помощью алгоритма слияния объедините подсписки в один отсортированный список. Рекурсия заканчивается, когда под-под-подсписок, переданный алгоритму сортировки, содержит всего один элемент, поскольку он, очевидно, является отсортированным.
Сортировка слиянием обладает только одним недостатком - алгоритм слияния требует наличия третьего списка, в котором будут храниться результаты слияния.
В отличие от всех ранее рассмотренных методов сортировки, которые сортируют элементы непосредственно в самом исходном списке, сортировка слиянием для работы требует большого дополнительного объема памяти. В качестве первого приближения в самой простой реализации может показаться, что для выполнения сортировки понадобиться новый вспомогательный список, размер которого равен сумме размеров двух исходных списков. Элементы из обоих списков будут помещаться во вспомогательный список, а затем после слияния - в основной список. Несмотря на то что можно разработать алгоритм, который выполняет операцию слияния, не требуя вспомогательного списка, на практике его выполнение занимает намного больше времени. Поэтому при необходимости применения сортировки слиянием нужно смириться с дополнительными требованиями в отношении памяти.
Сколько же памяти потребуется? Только что мы решили, что в худшем случае будет использоваться список, размер которого равен размеру исходного списка, но за счет небольшой хитрости можно снизить требования по дополнительной памяти до половины размера исходного списка.
Представьте себе, что мы находимся на самом верхнем уровне рекурсивного алгоритма. Только что мы выполнили сортировку двух половин исходного списка (будем считать, что первый отсортированный подсписок находится в первой половине списка, а второй - во второй половине), а теперь переходим к их слиянию. Вместо того чтобы выполнить слияние во вспомогательный список, равный по размеру исходному, скопируем первую половину списка в другой список, размер которого равен только половине исходного. Теперь у нас есть вспомогательный список, заполненный элементами из первой половины исходного списка, и исходный список, первая половина которого считается пустой, а вторая заполнена вторым подсписком элементов. При слиянии мы не перезапишем ни один из элементов второго подсписка, поскольку точно известно, что все содержимое вспомогательного списка может поместиться в свободную половину исходного списка.
Листинг 5.12. Стандартная сортировка слиянием
procedure MSS(aList : TList;
aFirst : integer;
aLast : integer;
aCoropare : TtdCompareFunc;
aTempList : PPointerList);
var
Mid : integer;
i, j : integer;
ToInx : integer;
FirstCount : integer;
begin
{вычислить среднюю точку}
Mid := (aFirst + aLast) div 2;
{выполнить рекурсивную сортировку слиянием первой и второй половин списка}
if (aFirst < Mid) then
MSS(aList, aFirst, Mid, aCompare, aTempList);
if (suce(Mid) < aLast) then
MSS(aList, succ(Mid), aLast, aCompare, aTempList);
{скопировать первую половину списка во вспомогательный список}
FirstCount := suce(Mid - aFirst);
Move(aList.List^[aFirst], aTempList^[0], FirstCount * sizeof(pointer));
{установить значения индексов: i - индекс для вспомогательного списка (т.е. первой половины списка), j - индекс для второй половины списка, ToInx - индекс в результирующем списке, куда будут копироваться отсортированные элементы}
i := 0;
j := suce (Mid);
ToInx := aFirst;
{выполнить слияние двух списков}
{повторять до тех пор, пока один из списков не опустеет}
while (i < FirstCount) and (j <= aLast) do
begin
{определить элемент с наименьшим значением из следующих элементов в обоих списках и скопировать его; увеличить значение соответствующего индекса}
if (aCompare(aTempList^[i], aList.List^[j]) <= 0) then begin
aList.List^[ToInx] := aTempList^[i];
inc( i );
end
else begin
aList.List^[ToInx] := aList.List^[j];
inc(j);
end;
{в объединенном списке есть еще один элемент}
inc(ToInx);
end;
{если в первом списке остались элементы, скопировать их}
if (i < FirstCount) then
Move(aTempList^[i], aList.List^[ToInx], (FirstCount - i) * sizeof(pointer));
{если во втором списке остались элементы, то они уже находятся в нужных позициях, значит, сортировка завершено; если второй список пуст, сортировка также завершена}
end;
procedure TDMergeSortStd(aList : TList;
aFirst : integer;
aLast : integer;
aCompare : TtdCompareFunc);
var
TempList : PPointerList;
ItemCount: integer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDMergeSortStd');
{если есть хотя бы два элемента для сортировки}
if (aFirst < aLast) then begin
{создать временный список указателей}
ItemCount := suce(aLast - aFirst);
GetMem(TempList, (suce(ItemCount) div 2) * sizeof(pointer));
try
MSS(aList, aFirst, aLast, aCompare, TempList);
finally
FreeMem(TempList, (suce(ItemCount) div 2) * sizeof(pointer));
end;
end;
end;
Если вы внимательно изучите код, приведенный в листинге 5.12, то обнаружите, что он содержит процедуру-драйвер, TDMergeSortStd, которая вызывается для выполнения сортировки списка, и отдельную вспомогательную процедуру, MSS, выполняющую рекурсивную сортировку. Прежде всего, процедура TDMergeSortStd проверяет попадание индекса в допустимые пределы и сам список, а затем - присутствуют ли в списке хотя бы два элемента, которые можно сортировать. После этого создается вспомогательный список указателей с размером, достаточным для хранения половины количества элементов исходного массива. Далее вызывается рекурсивная процедура MSS.
Процедура MSS рекурсивно вызывает сама себя для сортировки первой и второй половин переданной ей части массива. Затем она копирует первую половину во вспомогательный массив. Начиная с этого момента, код представляет собой стандартную реализацию сортировки слиянием, копируя две половины списка в исходный список. Если после выполнения цикла сравнения и копирования во вспомогательном массиве остались элементы, процедура MSS их просто копирует. Если же элементы остались во второй половине списка, их можно не копировать, как и в стандартной реализации метода слияния: они уже находятся на своих местах.
Вывод функции быстродействия сортировки слиянием достаточно сложен. Для простоты ее определения лучше принять, что в исходном списке находится 2(^х^) элементов. Предположим, что элементов 32. На первом уровне рекурсии процедура MSS будет вызываться один раз и на этапе слияния будет не более 32 сравнений. На втором уровне рекурсии процедура MSS будет вызываться два раза, причем количество сравнений при каждом вызове не будет превышать 16. Далее рассматриваем третий, четвертый и, наконец, пятый уровень рекурсии (когда будет выполняться сортировка всего двух элементов), на котором будет иметь место 16 вызовов процедуры по два сравнения в каждом. Таким образом, общее количество сравнений будет равно 5 * 32. Но причиной, по которой было получено пять уровней рекурсии, является то, что мы постоянно на каждом уровне постепенно делили список на две равные половины, а 2(^5^) = 32, что, естественно означает, что log(_2_)32 = 5. Следовательно, не утруждая себя переходом от рассмотренного нами частного случая к общему, можно сказать, что сортировка слиянием принадлежит к классу O(n log(n)) алгоритмов.
Что касается устойчивости, то поскольку элементы перемещаются только при выполнении процедуры слияния, устойчивость всей сортировки слиянием будет зависеть от устойчивости самого слияния двух половин списка. Обратите внимание, что если в обеих половинах имеются элементы с одинаковым значением, то оператор сравнения гарантирует, что первым в результирующий список попадет элемент из первой половины списка. Это означает, что операция слияния сохраняет относительный порядок элементов, и, следовательно, сортировка слиянием будет устойчивой.
Если отслеживать вызовы процедуры MSS в отладчике, то можно обратить внимание, что для небольших интервалов она вызывается очень часто. Например, если в списке содержится 32 элемента, то для списка из 32 элементов процедура MSS будет вызвана один раз, для списка из 16 элементов - дважды, четыре раза для 8 элементов, восемь раз для 4 элементов и шестнадцать раз для 2 элементов (список минимальной длины), т.е. всего 31 раз. Это очень много, особенно если учитывать, что большая часть вызовов (29) приходится для списков длиной восемь и менее элементов. Если бы исходный список содержал 1024 элемента, процедура MSS была бы вызвана 1023 раза, из которых 896 вызовов приходилось бы на долю списков длиной восемь и менее элементов. Просто ужасно! Фактически, для сортировки коротких списков было бы эффективнее использовать нерекурсивный алгоритм. Это позволило бы повысить скорость всей сортировки. Кроме того, применение более простой процедуры дало бы возможность для коротких диапазонов исключить копирование элементов между основным и вспомогательным списком. И одним из лучших методов для ускорения сортировки слиянием является сортировка методом вставок.
