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

<p>Самые быстрые алгоритмы сортировки</p>

И вот, наконец, мы добрались до самых быстрых алгоритмов сортировки. Они очень широко используются на практике и очень важно понимать их особенности, что позволит оптимальным образом реализовывать их в различных приложениях.

<p>Сортировка слиянием</p>
Перейти на страницу:

Похожие книги

C++
C++

С++ – это универсальный язык программирования, задуманный так, чтобы сделать программирование более приятным для серьезного программиста. За исключением второстепенных деталей С++ является надмножеством языка программирования C. Помимо возможностей, которые дает C, С++ предоставляет гибкие и эффективные средства определения новых типов. Используя определения новых типов, точно отвечающих концепциям приложения, программист может разделять разрабатываемую программу на легко поддающиеся контролю части. Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определенных пользователем. Такие объекты просты и надежны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. Программирование с применением таких объектов часто называют объектно-ориентированным. При правильном использовании этот метод дает более короткие, проще понимаемые и легче контролируемые программы. Ключевым понятием С++ является класс. Класс – это тип, определяемый пользователем. Классы обеспечивают сокрытие данных, гарантированную инициализацию данных, неявное преобразование типов для типов, определенных пользователем, динамическое задание типа, контролируемое пользователем управление памятью и механизмы перегрузки операций. С++ предоставляет гораздо лучшие, чем в C, средства выражения модульности программы и проверки типов. В языке есть также усовершенствования, не связанные непосредственно с классами, включающие в себя символические константы, inline-подстановку функций, параметры функции по умолчанию, перегруженные имена функций, операции управления свободной памятью и ссылочный тип. В С++ сохранены возможности языка C по работе с основными объектами аппаратного обеспечения (биты, байты, слова, адреса и т.п.). Это позволяет весьма эффективно реализовывать типы, определяемые пользователем. С++ и его стандартные библиотеки спроектированы так, чтобы обеспечивать переносимость. Имеющаяся на текущий момент реализация языка будет идти в большинстве систем, поддерживающих C. Из С++ программ можно использовать C библиотеки, и с С++ можно использовать большую часть инструментальных средств, поддерживающих программирование на C. Эта книга предназначена главным образом для того, чтобы помочь серьезным программистам изучить язык и применять его в нетривиальных проектах. В ней дано полное описание С++, много примеров и еще больше фрагментов программ.

Бьёрн Страуструп , Бьярн Страустрап , Мюррей Хилл

Программирование, программы, базы данных / Программирование / Книги по IT