{упорядочить два элемента, отстоящих друг от друга на Gap элементов}
for i := aFirst to (aLast - Gap) do
begin
j := i + Gap;
if (aCompare(aList.List^[j], aList.List^[i]) < 0) then begin
{поменять местами элементы с индексами j и (j-Gap)}
Temp := aList.List^[j];
aList.List^[j] := aList.List^[i];
aList.List^[i] := Temp;
{была выполнена перестановка, следовательно, сортировка не завершена}
Done := false;
end;
end;
until Done and (Gap = 1);
end;
В экспериментах, проведенных автором книги, сортировка методом прочесывания была немного быстрее сортировки методом Шелла (на последовательности Кнута). Кроме того, ее легче запрограммировать (если не говорить о необходимости исключения расстояний 9 и 10). Очевидно, что сортировка методом прочесывания, как и методом Шелла, принадлежит к группе неустойчивых алгоритмов.
Самые быстрые алгоритмы сортировки
И вот, наконец, мы добрались до самых быстрых алгоритмов сортировки. Они очень широко используются на практике и очень важно понимать их особенности, что позволит оптимальным образом реализовывать их в различных приложениях.
Сортировка слиянием
Сортировка слиянием (merge sort) считается весьма интересным алгоритмом. Она привлекательна своей простотой и наличием некоторых важных особенностей (например, она принадлежит к алгоритмам класса O(n log(w)) и не имеет худших случаев), но если приступить к его реализации, можно натолкнуться на большую проблему. Тем не менее, сортировка слиянием очень широко используется при необходимости сортировки содержимого файлов, размер которых слишком велик, чтобы поместиться в памяти.
Мы будет рассматривать сортировку слиянием по шагам, начиная со слияния. Затем мы опишем, как использовать алгоритм для выполнения сортировки. В качестве примера мы не будем пользоваться картами - алгоритм легко понять и без карт.
Представьте себе, что имеется два уже отсортированных списка и необходимо сформировать один список, объединяющий все элементы исходных списков. План А состоит в том, чтобы скопировать оба списка в результирующий и выполнить его сортировку. Но в этом случае, к сожалению, мы не пользуемся тем, что исходные списки уже отсортированы. План Б предусматривает слияние. Смотрим на первые элементы в обоих списках. Элемент с меньшим значением переносим в результирующий список. Снова смотрим на первые элементы в обоих списках и снова переносим в результирующий список элемент с меньшим значением, удаляя его из исходного списка. Описанный процесс продолжается до тех пор, пока не исчерпаются элементы одного из списков. После этого в результирующий список можно перенести все оставшиеся в исходном списке элементы. Такой алгоритм формально известен под названием алгоритма двухпутевого слияния (two-way merge algorithm ).
Конечно, на практике элементы не удаляются из исходных списков. Вместо удаления используются указатели на текущие начальные элементы списков, которые при копировании передвигаются на следующий элемент.
Листинг 5.11. Слияние двух отсортированных массивов TList
procedure TDListMerge( aList 1, aList2, aTarget List : TList;
aCompare : TtdCompareFunc);
var
Inx1, Inx2, Inx3 : integer;
begin
{подготовить результирующий список}
aTargetList.Clear;
aTargetList.Capacity := aList1.Count + aList2.Count;
{инициализировать счетчики}
Inx1 := 0;
Inx2 := 0;
Inx3 := 0;
{выполнять цикл до исчерпания элементов одного из списка...}
while (Inx1 < aList1.Count) and (Inx2 < aList2.Count) do
begin
{определить наименьшее значение из двух списков и скопировать его в результирующий список; увеличить значения индексов на единицу}
if aCompare (aList1.List^[Inx1], aList2.List^[Inx]) < = 0 then begin
aTargetList.List^[Inx3] := aList1.List^[Inx1];
inc(Inx1);
end
else begin
aTargetList.List^[Inx3] := aList2.List^[Inx2];
inc(Inx2);
end;
inc(Inx3);
end;
{выполнение цикла прекращается при исчерпании элементов одного из списков; если в первом списке еще остались элементы, скопировать их в результирующий список}
if (Inx1 < aList1.Count) then
Move(aList1.List^[Inx1], aTargetList.List^[Inx3],
(aList1.Count - Inx1) * sizeof(pointer)) {в противном случае скопировать все элементы, оставшиеся во втором списке, в результирующий список}
else
Move(aList2.List^[Inx2], aTargetList.List^[Inx3], (aList2.Count - Inx2) * sizeof(pointer));
end;
Обратите внимание, что в коде копирование оставшихся элементов в одном или другом списке выполняется с помощью процедуры Move. Для копирования можно было бы организовать небольшой цикл, однако процедура Move работает намного быстрее.
Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих исходных списках. Если в первом из них находится n элементов, а во втором - m, нетрудно прийти к выводу, что в
