Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Время выполнения.
Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году. Это алгоритм сортировки массива произвольных элементов; требуемый им дополнительный объём памяти не зависит от количества исходных данных. Время работы алгоритма — в среднем, а также в лучшем и худшем случаях.
Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.
Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:
Каждый лист имеет глубину либо, либо, — максимальная глубина дерева.
Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.
Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] являются Array[2i] и Array[2i+1].
Алгоритм сортировки будет состоять из двух основных шагов:
1. Выстраиваем элементы массива в виде сортирующего дерева:
при.
Этот шаг требует операций.
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(1) дополнительной памяти (если дерево организовывать так, как показано выше).
Недостатки
Сложен в реализации.
Неустойчив — для обеспечения устойчивости нужно расширять ключ.
На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
Не работает на связанных списках и других структурах памяти последовательного доступа
Сортировка слиянием при расходе памяти O(n) быстрее (с меньшей константой) и не подвержена деградации на неудачных данных.
Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.
Пример
def heapsort(s):
sl = len(s)
def swap(pi, ci):
if s[pi] < s[ci]:
s[pi], s[ci] = s[ci], s[pi]
def sift(pi, unsorted):
i_gt = lambda a, b: a if s[a] > s[b] else b
while pi*2+1 < unsorted:
gtci = i_gt(pi*2+1, pi*2+2) if pi*2+2 < unsorted else pi*2+1
Дата публикования: 2014-12-08; Прочитано: 784 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!