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

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

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

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

Листинг 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.