Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Листинг 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).
Поскольку в приведенном коде для сортировки коротких диапазонов в списке используется сортировка методом вставок, которая сама по себе является устойчивой, можно сказать, что оптимизированная сортировка слиянием также принадлежит к группе устойчивых алгоритмов.
Несмотря на то что сортировка слиянием требует дополнительной памяти (объем которой пропорционален количеству элементов в исходном списке), она обладает некоторыми интересными свойствами. Первое из них - сортировка слиянием принадлежит к классу O(n log(n)). Второе - она устойчива. Еще два алгоритма со скоростью работы O(n log(n)) и дополнительными требованиями к памяти, которые будут рассмотрены в этой главе, являются неустойчивыми. Третье - для сортировки слиянием не имеет значения ни порядок элементов в исходном списке (будь то список, отсортированный в прямом порядке или обратном), ни повторения значений в списке. Другими словами, она не имеет худшего случая.
В конце этой главы мы рассмотрим случай, в котором сортировка слиянием просто необходима, - сортировка связного списка.
И, наконец, сортировка слиянием используется для сортировки содержимого файлов, размер которых слишком велик, чтобы поместиться в памяти. В этой ситуации выполняется сортировка частей файлов, запись этих частей в отдельные файлы, а затем их слияние в один файл.
Быстрая сортировка
И последний алгоритм, который будет рассмотрен в этой главе - быстрая сортировка (quicksort). (В книге мы опишем еще одну сортировку "в памяти" - пирамидальную сортировку, но она требует дополнительных знаний структуры данных - бинарного дерева. По этой причине рассмотрение пирамидальной сортировки отложено до главы 9.)
Алгоритм быстрой сортировки был разработан К.A.Р. Хоаром (C.A.R. Hoare) в 1960 году. Этот алгоритм, наверное, еще более известен, чем пузырьковая сортировка. В настоящее время он является самым широко используемым в программировании методом сортировки, что вызвано его крайне положительными характеристиками: это алгоритм класса O(n log(n)) для общего случая, он требует лишь незначительного объема дополнительной памяти, работает с различными типами входных списков и достаточно удобен для реализации. Но, к сожалению, быстрая сортировка имеет и несколько нежелательных характеристик: при его реализации допускается очень много ошибок (простые ошибки в реализации могут остаться незамеченными и при выполнении могут потребовать дополнительного времени), быстродействие в худшем случае составляет O(n(^2^)) и к тому же она неустойчива.
Кроме того, быстрая сортировка наиболее изучена. Со времени выхода в свет первой статьи Хоара многие исследователи изучали быструю сортировку и сформировали значительную базу данных по теоретическому определению времени выполнения, подкрепленную эмпирическими данными. Было предложено немало улучшений базового алгоритма, позволяющих увеличить скорость работы. Некоторые из предложенных улучшений будет рассмотрены в этой главе. При таком богатстве литературных источников по алгоритму быстрой сортировки, если следовать всем рекомендациям, у вас не должно возникнуть проблем с реализацией. (В последней оптимизированной реализации алгоритма использовалось более шести различных справочных пособий по алгоритмам. Причем в одной из них была приведена "оптимизированная" быстрая сортировка, которая была написана так плохо, что при одних и тех же входных данных работала даже медленнее, чем стандартный метод TList.Sort.)
Быстрая сортировка встречается везде. Во всех версиях Delphi, за исключением версии 1, метод TList.Sort реализован на основе алгоритма быстрой сортировки. Метод TStringList.Sort во всех версиях Delphi реализован с помощью быстрой сортировки. В С++ функция qsort из стандартной библиотеки времени выполнения также реализована на базе быстрой сортировки.
Основной алгоритм быстрой сортировки, как и сортировку слиянием, можно отнести к классу "разделяй и властвуй". Он разбивает исходный список на два, а затем для выполнения сортировки рекурсивно вызывает сам себя для каждой части списка. Таким образом, особое внимание в быстрой сортировке нужно уделить процессу разделения. В разбитом списке происходит следующее: выбирается элемент, называемый базовым, относительно которого переставляются элементы в списке. Элементы, значения которых меньше, чем значение базового элемента, переносятся левее базового, а элементы, значения которых больше, чем значение базового элемента, переносятся правее базового. После этого можно сказать, что базовый элемент находится на своем месте в отсортированном списке. Затем выполняется рекурсивный вызов функции быстрой сортировки для левой и правой частей списка (относительно базового элемента). Рекурсивные вызовы прекращаются, когда список, переданный функции сортировки, будет содержать всего один элемент, а, следовательно, весь список оказывается отсортированным.
