Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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).
Поскольку в приведенном коде для сортировки коротких диапазонов в списке используется сортировка методом вставок, которая сама по себе является устойчивой, можно сказать, что оптимизированная сортировка слиянием также принадлежит к группе устойчивых алгоритмов.
Несмотря на то что сортировка слиянием требует дополнительной памяти (объем которой пропорционален количеству элементов в исходном списке), она обладает некоторыми интересными свойствами. Первое из них - сортировка слиянием принадлежит к классу O(n log(n)). Второе - она устойчива. Еще два алгоритма со скоростью работы O(n log(n)) и дополнительными требованиями к памяти, которые будут рассмотрены в этой главе, являются неустойчивыми. Третье - для сортировки слиянием не имеет значения ни порядок элементов в исходном списке (будь то список, отсортированный в прямом порядке или обратном), ни повторения значений в списке. Другими словами, она не имеет худшего случая.
В конце этой главы мы рассмотрим случай, в котором сортировка слиянием просто необходима, - сортировка связного списка.
И, наконец, сортировка слиянием используется для сортировки содержимого файлов, размер которых слишком велик, чтобы поместиться в памяти. В этой ситуации выполняется сортировка частей файлов, запись этих частей в отдельные файлы, а затем их слияние в один файл.
Быстрая сортировка
И последний алгоритм, который будет рассмотрен в этой главе - быстрая сортировка (quicksort). (В книге мы опишем еще одну сортировку "в памяти" - пирамидальную сортировку, но она требует дополнительных знаний структуры данных - бинарного дерева. По этой причине рассмотрение пирамидальной сортировки отложено до главы 9.)