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

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

на обложку

Бакнелл Джулиан М.

Шрифт:

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;

Если вы внимательно изучите код, приведенный в листинге 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 вызовов приходилось бы на долю списков длиной восемь и менее элементов. Просто ужасно! Фактически, для сортировки коротких списков было бы эффективнее использовать нерекурсивный алгоритм. Это позволило бы повысить скорость всей сортировки. Кроме того, применение более простой процедуры дало бы возможность для коротких диапазонов исключить копирование элементов между основным и вспомогательным списком. И одним из лучших методов для ускорения сортировки слиянием является сортировка методом вставок.

Листинг 5.13. Оптимизированная сортировка слиянием

const

MSCutOff = 16;

procedure MSInsertionSort(aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

IndexOfMin : integer;

Temp : pointer;

begin

{найти наименьший элемент в списке}