Читать онлайн «Фундаментальные алгоритмы и структуры данных в Delphi». Страница 37

h := 1;

Ninth := (aLast - aFirst) div 9;

while (h<= Ninth) do h := (h * 3) + 1;

{начать выполнение цикла, который при каждом проходе уменьшает значение h на треть}

while (h > 0) do

begin

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

for i := (aFirst + h) to aLast do

begin

Temp := aList.List^[i];

j := i;

while (j >= (aFirst+h)) and

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

begin

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

dec(j, h);

end;

aList.List^[j ] := Teilend;

{уменьшить значение h на треть}

h := h div 3;

end;

end;

Математические зависимости для анализа быстродействия сортировки методом Шелла достаточно сложны. В общем случае для оценки времени выполнения сортировки при различных значениях h приходится ограничиваться статистическими данными. Тем не менее, анализ быстродействия алгоритма Шелла практически не имеет смысла, поскольку существуют более быстрые алгоритмы.

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

Этот раздел будет посвящен действительно странному алгоритму сортировки -сортировке методом прочесывания (comb sort). Он не относится к стандартным алгоритмам. На сегодняшний день он малоизвестен и поиск информации по нему может не дать никаких результатов. Тем не менее, он отличается достаточно высоким уровнем быстродействия и удобной реализацией. Метод был разработан Стефаном Лейси (Stephan Lacey) и Ричардом Боксом (Richard Box) и опубликован в журнале "Byte" в апреле 1991 года. Фактически он использует пузырьковую сортировку таким же образом, как сортировка методом Шелла использует сортировку методом вставок.

Перетасуйте карты и снова разложите их на столе. Выделите первую и девятую карту. Если они находятся в неправильном порядке, поменяйте их местами. Выделите вторую и десятую карты и, при необходимости, поменяйте их местами. То же самое проделайте для третьей и одиннадцатой карты, четвертой и двенадцатой, а затем пятой и тринадцатой. Далее сравнивайте и переставляйте пары карт (1, 7), (2, 8), (3, 9), (4, 10), (5, 11), (6, 12) и (7, 13) (т.е. карты, отстоящие друг от друга на шесть позиций). А теперь выполните проход по колоде для карт, отстоящих друг от друга на четыре позиции, затем на три и две позиции. После этого выполните стандартную пузырьковую сортировку (которую можно рассматривать как продолжение предыдущего алгоритма для соседних карт).

Таким образом, вначале карты большими "прыжками" передвигаются в требуемую область. Как и сортировка методом Шелла, прочесывание неудобно выполнять на картах, но в функции для сортировки методом прочесывания требуется всего два цикла - один для уменьшения размера "прыжков", а второй - для выполнения разновидности пузырьковой сортировки.

Как были получены значения расстояний 8, 6, 4, 3, 2, 1? Разработчики этого метода сортировки провели большое количество экспериментов и эмпирическим путем пришли к выводу, что значение каждого последующего расстояния "прыжка" должно быть получено в результате деления предыдущего на 1.3. Этот "коэффициент уменьшения" был лучшим из рассмотренных и позволял сбалансировать зависимость времени выполнения от длины последовательности значений расстояний и времени выполнения пузырьковой сортировки.

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

Рисунок 5.7. Сортировка методом прочесывания (показаны только перестановки)

Листинг 5.10. Сортировка методом прочесывания

procedure TDCombSort(aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

Temp : pointer;

Done : boolean;

Gap : integer;

begin

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

{начать с расстояния, равного количеству элементов}

Gap := succ(aLast - aFirst);

repeat

{предположить, что сортировка будет выполнена на этом проходе}

Done := true;

{calculate the new gap}

Gap := (longint(Gap) * 10) div 13;

{Gap := Trunc(Gap / 1.3);}

if (Gap < 1) then

Gap := 1

else

if (Gap = 9) or (Gap = 10) then

Gap := 11;

{упорядочить два элемента, отстоящих друг от друга на 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 работает намного быстрее.