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

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

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

Этот раздел будет посвящен действительно странному алгоритму сортировки -сортировке методом прочесывания (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). Очевидно, что сортировка методом прочесывания, как и методом Шелла, принадлежит к группе неустойчивых алгоритмов.

Оглавление книги