Улучшенные методы сортировки массивов.

К улучшенным методам сортировки массивов относятся:

- сортировка Шелла

- сортировка кучей

- быстрая сортировка (qsort)

 

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

 

Сортировка Шелла – это алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея этого метода состоит в том, чтобы сравнивать не только те элементы, которые стоят рядом, но и на определенном расстоянии друг от друга (сортировка вставками с предварительными "грубыми" проходами).

 

Была названа в честь ее изобретателя – Дональда Шелла (1959 год).

 

Алгоритм:

- Сначала сравниваются и сортируются между собой значения, отстоящие друг от друга на расстоянии D (подбирается эмпирически).

- Эта процедура повторяется для меньших значений D, и завершается сортировка упорядочиванием элементов при d = 1 (т.е. стоящих рядом; обычная сортировка вставками).

 

Несмотря на то, что эта сортировка во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

- отсутствие потребности в памяти под стек;

- отсутствие деградации при неудачных наборах данных.

 

; в качестве значений выбраны .

На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки , , , ,

Среднее время работы алгоритма зависит от длин промежутков – D, на которых будут находиться сортируемые элементы исходного массива емкостью N на каждом шаге алгоритма.

 

Недостатки:

- во многих случаях медленнее, чем быстрая сортировка.

- является неустойчивым алгоритмом.

 

Сортировка кучей.

 

Сортировка кучей – алгоритм сортировки, работающий в худшем, среднем и лучшем случае за гарантированное время O(n log(n)) операций при сортировке n элементов.

 

Количество применяемой служебной памяти не зависит от размера массива (т.е. O(1)).

 

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

 

Была предложена Дж. Уильямсом в 1964 году.

 

Алгоритм:

- Элементы массива выстраиваются в виде сортирующего дерева. Сортирующее дерево – такое дерево, для которого выполняются условия:

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

- Значение в любой вершине не меньше (или не больше при min-куче) значения ее потомков.

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

 

- Элементы в сортирующем дереве удаляются по одному из корня за раз, и дерево перестраивается (т.е. на первом шаге обмениваются A[1] и A[n], на втором – A[1] и A[n-1], и т.д.), до того, пока в сортирующем массиве не останется один элемент. Тогда A будет являться упорядоченной последовательностью.

Данный шаг требует O(n log(n)) операций.

 

Достоинства:

- имеет доказанную оценку худшего случая O(n log(n));

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

 

Недостатки:

- сложен в реализации;

- неустойчив;

- неестественен;

- на каждом шаге выборку приходится делать хаотично по всей длине массива (плохо сочетается с кэшированием и подкачкой памяти)

- не работает на связанных списках и других структурах памяти последовательного доступа.

 

Из-за сложности алгоритма выигрыш получается только на больших n.

 

Быстрая сортировка.

Быстрая сортировка – широко известный алгоритм сортировки, являющийся одним из самых быстрых универсальных алгоритмов сортировки массивов (в среднем O(n log(n))). Из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

 

Алгоритм:

- Выбрать из массива элемент, называемый опорным (может быть любой из элементов массива).

- Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на 3 непрерывных отрезка, следующих друг за другом: меньшие опорного, равные и большие.

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

 

Обычно массив делят не на 3 части, а на 2: меньшие опорного и равные или большие.

 

Достоинства:

- Один из самых быстрых алгоритмов внутренней сортировки общего назначения.

- Прост в реализации.

- Требует лишь O(lg(n)) дополнительной памяти для своей работы (не улучшенный рекурсивный алгоритм – O(n)).

- Работает на связных списках и других структурах последовательнго доступа.

 

Недостатки:

- Сильно деградирует по скорости в худшем или близком к нему случае (O(n^2)).

- Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека.