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

Процедура 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

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

IndexOfMin := aFirst;

for i := succ(aFirst) to aLast do

if (aCompare(aList.List^[i], aList.List^[IndexOfMin]) < 0) then

IndexOfMin := i;

if (aFirst <> indexOfMin) then begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[IndexOfMin];

aList.List^[IndexOfMin] := Temp;

end;

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

for i := aFirst+2 to aLast do

begin

Temp := aList.List^[i];

j := i;

while (aCompare(Temp, aList.List^[j-1]) < 0) do

begin

aList.List^[j] := aList.List^[j-1];

dec(j);

end;

aList.List^[j] := Temp;

end;

end;

procedure MS(aList : TList; aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc;

aTempList : PPointerList);

var

Mid : integer;

is j : integer;

ToInx : integer;

FirstCount : integer;

begin

{вычислить среднюю точку}

Mid := (aFirst + aLast) div 2;

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

if (aFirst < Mid) then

if (Mid-aFirst) <= MSCutOff then

MSInsertionSort(aList, aFirst, Mid, aCompare) else

MS (aList, aFirst, Mid, aCompare, aTempList);

{аналогично выполнить сортировку второй половины}

if (suce(Mid) < aLast) then

if (aLast-succ(Mid) ) <= MSCutOf f then

MSInsertionSort(aList, succ(Mid), aLast, aCompare)

else

MS (aList, suce(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 TDMergeSort(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

TempList : PPointerList;

ItemCount: integer;

begin

TDValidateListRange(aList, aFirst, aLast, 'TDMergeSort');

{если есть хотя бы два элемента для сортировки}

if (aFirst < aLast) then begin

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

ItemCount := suce (aLast - aFirst);

GetMem(TempList, (succ(ItemCount) div 2) * sizeof(pointer));

try

MS(aList, aFirst, aLast, aCompare, TempList);

finally

FreeMem(TempList, (succ(ItemCount) div 2) * sizeof(pointer));

end;

end;

end;

Несмотря на то что объем кода достаточно велик, в нем находятся всего три процедуры. Прежде всего, драйвер - TDMergeSort - процедура, которую мы вызываем. Как и в предыдущем случае, она используется для выделения из кучи памяти под вспомогательный список указателей и вызывает рекурсивную процедуру, названную в приведенном коде MS. В общих чертах процедура MS работает примерно так, как и ее предшественница - MSS (рекурсивная процедура для стандартной сортировки слиянием). Разница возникает только тогда, когда дело касается сортировки подсписков. Для небольших диапазонов элементов, длина которых меньше, чем значение MSCutOff, процедура MS вызывает третью процедуру, MSInsertionSort, которая сортирует элементы без рекурсивного вызова. Для длинных диапазонов элементов, естественно, происходит рекурсивный вызов процедуры MS. MSInsertionSort ничем не отличается от рассмотренной нами ранее процедуры TDInsertionSort, за исключением одного - она не проверяет корректность входных параметров (в проверке нет необходимости, поскольку все параметры были проверены в TDMergeSort).