Реферат Курсовая Конспект
Пирамидальная сортировка - раздел Образование, Сортировка, пирамидальная сортировка. Параметры задачи: размер последовательности, длина строки. Мера сравнения: число обменов, число сравнений, Время выполнения. Пирамидальная Сортировка Была Предложена Дж. Уильямсом В 1964 Го...
|
Пирамидальная сортировка была предложена Дж. Уильямсом в 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 (до нескольких тысяч) быстрее сортировка Шелла.
– Конец работы –
Эта тема принадлежит разделу:
Сортировка пирамидальная сортировка Параметры задачи размер... последовательности длина строки Мера сравнения число обменов число... Время выполнения Пирамидальная сортировка Пирамидальная...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Пирамидальная сортировка
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов