15. Сортировка Шелла

это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морс- ких ракушек друг на друга. ("Ракушка" - одно из значений слова shell - Примеч. пер.)

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

проход 1   f   d   a   c   b   e проход 2   c   b   a   f   d   e проход 3   a   b   c   e   d   f полученный результат   a   b   c   d   e    f { сортировка Шелла } procedure Shell(var item: DataArray; count:integer); const t = 5; var i, j, k, s, m: integer; h: array[1..t] of integer; x: DataItem; begin h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1; for m := 1 to t do begin k:=h[m]; s:=-k; for i := k+1 to count do begin x := item[i]; j := i-k; if s=0 then begin s := -k; s := s+1; item[s] := x; end; while () do begin item[j+k] := item[j]; j := j-k; end; item[j+k] := x; end;end;end; { конец сортировки Шелла } Эффективность этого алгоритма объясняется тем, что при каждом проходе ис- пользуется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.

16. Пирамидальная сортировка

Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.^[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое двоичное дерево, у которого выполнены условия:

Каждый лист имеет глубину либо d, либо d − 1, d — максимальная глубина дерева.

Значение в любой вершине больше, чем значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] —Array[2i] и Array[2i+1].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева:

при  .

Этот шаг требует O(n) операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.

Этот шаг требует O(nlogn) операций.

Достоинства и недостатки

Имеет доказанную оценку худшего случая O(nlogn).

Требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Сложен в реализации.

Неустойчив — для обеспечения устойчивости нужно расширять ключ.

На почти отсортированных массивах работает столь же долго, как и на хаотических данных.

На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.