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

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

Какие значения к лучше всего использовать? Шелл в своей первой статье на эту тему предложил значения 1, 2, 4, 8, 16, 32 и т.д. (естественно, в обратном порядке), но с этими значениями связана одна проблема: до последнего прохода элементы с четными индексами никогда не сравниваются с элементами с нечетными индексами. И, следовательно, при выполнении последнего прохода все еще возможны перемещения элементов на большие расстояния (представьте себе, например, искусственный случай, когда элементы с меньшими значениями находятся в позициях с четными индексами, а элементы с большими значениями - в позициях с нечетными индексами).

Рисунок 5.6. Сортировка методом Шелла

В 1969 году Дональд Кнут (Donald Knuth) предложил последовательность 1, 4, 13, 40, 121 и т.д. (каждое последующее значение на единицу больше, чем утроенное предыдущее значение). Для списков средних размеров эта последовательность позволяет получить достаточно высокие характеристики быстродействия (на основе эмпирических исследований Кнут оценил быстродействие для среднего случая как O(n(^5/4^)), а для худшего случая было доказано, что скорость работы равна O(n(^3/2^))) при несложном методе вычисления значений самой последовательности. Ряд других последовательностей позволяют получить более высокие значения скорости работы (хотя и не намного), но требуют предварительного вычисления значений последовательности, поскольку используемые формулы достаточно сложны. В качестве примера можно привести самую быструю известную на сегодняшний день последовательность, разработанную Робертом Седжвиком (Robert Sedgewick): 1, 5, 19, 41, 109 и т.д. (формируется путем слияния двух последовательностей — 9 * 4i - 9 * 2i + 1 для i > 0 и 4i - 3 * 2i + 1 для i > 1). Известно, что для этой последовательности время работы в худшем случае определяется как O(n(^4/3^)) при O(n(^7/6^)) для среднего случая. В этой книге мы не будем приводить математические выкладки для определения приведенных зависимостей. Пока не известно, существуют ли еще более быстрые последовательности. (подробнейшие выкладки и анализ всех фундаментальных алгоритмов, в числе которых и алгоритмы, рассмотренные в данной книге, а также эффективная их реализация на языках С, С++ и Java, можно найти в многотомниках Роберта Седжвика "Фундаментальные алгоритмы на С++", "Фундаментальные алгоритмы на С" и "Фундаментальные алгоритмы на Java", которые выпущены издательством "Диасофт".)

Листинг 5.9. Сортировка методом Шелла при использовании последовательности Кнута

procedure TDShellSort(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

h : integer;

Temp : pointer;

Ninth : integer;

begin

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

{прежде всего вычисляем начальное значение h; оно должно быть близко к одной девятой количества элементов в списке}

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

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

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

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

C++
C++

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

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

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