53462

Оптимизация процедуры Heap_sort, особенности

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-04-01

19.42 KB

0 чел.

Оптимизация процедуры Heap_sort, особенности.

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году. Это алгоритм сортировки массива произвольных элементов; требуемый им дополнительный объём памяти не зависит от количества исходных данных. Время работы алгоритма — O(n*ln n)в среднем, а также в лучшем и худшем случаях.

Идея алгоритма:

  1. Для того, чтобы прояснить всё дальнейшее изложение, в двух словах опишу идею алгоритма.
  2. Пирамида — двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.
  3. Заполнив дерево элементами в произвольном порядке, можно легко его отсортировать (легче, чем исходный список элементов), превратив в пирамиду.
  4. Самый большой элемент пирамиды находится в её вершине.
  5. Отделяем вершинный элемент, и записываем его в конец результирующего массива.
  6. На место вершинного элемента записываем элемент из самого нижнего уровня дерева.
  7. Восстанавливаем (пересортировываем) пирамиду.
  8. Самый большой элемент из оставшихся снова в вершине. Снова отделяем его и записываем его в качестве предпоследнего элемента результата, и так далее...
  9. Весь фокус алгоритма в том, что пирамида без дополнительных затрат хранится прямо в исходном массиве. По мере того, как размер пирамиды уменьшается, она занимает всё меньшую часть массива, а результат сортировки записывается начиная с конца массива на освободившиеся от пирамиды места. Достоинства:
  10. Имеет доказанную оценку худшего случая O(n*log n)
  11. Сортирует на месте, то есть требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки: Сложен в реализации.

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

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

82214. Вклонімося хлібу – він святий 71.5 KB
  Виріс у полі на добрій землі Місце найкраще знайшов на столі Що це Учні відповідають: Хліб Слайд Ведуча: Хліб - найдорогоцінніший витвір людського розуму людських рук людської праці Ведуча: Хліб усьому голова. Але до хліба не можна ставитися побуденному. В чому ж ця сила і велич хліба ми спробуємо...
82215. Людиною стати – це мистецтво 76 KB
  Мета: навчити учнів уникати конфлікту у житті, вміти спілкуватися, дружити між собою; розвивати в дітях загальнолюдські чесноти; вчити дітей сприймати ситуації, аналізувати їх і знаходити шляхи виходу з проблемних ситуацій; виховувати товариські стосунки.
82216. Давайте жить мирно! 58.5 KB
  Внекласное мероприятие Давайте жить мирно проведённое в международный День мира направлено на формирование у учащихся чувства сострадания и отвращения к жестокости к жестоким историческим фрагментам во всем мире; на обучение осознанию своей ответственности за процесс обеспечения мира на всей планете.
82217. ДЕНЬ ПРАЦІВНИКА ОСВІТИ 1.09 MB
  Ведучий: Красива осінь вишиває клени, а перший день жовтня дарує нам тепле і радісне свято - День працівника освіти. Викладач... Одна з найважливіших професій. Вона – для обраних. Ви щодня стоїте перед прицілом сотень допитлитвих очей, палите, як хмиз, нерви, і все ж ведете нас на вищі сходинки пізнання.
82218. Воздух – среда нашего обитания 944.87 KB
  Цели: Практическая – учить использовать разные источники, в том числе Интернет (электронные словари и энциклопедии)для поиска необходимой информации. Совершенствовать навыки практической работы с лабораторным оборудованием.
82219. Дружба. Друг, товариш, приятель 1.47 MB
  Передаючи мікрофон діти по черзі висловлюють свою думку на рахунок даного запитання кожен з них виокремлює по одній рисі характеру що притаманна другові. А як на вашу думку хто з казкових чи мультиплікаційних героїв є прикладом справжнього другадіти висловлюють власні припущення.
82220. Хліб – не просто їжа 273 KB
  Запитання: то з яким продуктом харчування ми зустрічаємося кожен день Сьогодні ми поговоримо з вами про найдорожче золото на землі хліб. Коли ж хліб вперше прийшов на стіл до людини Вченіархеологи різних країн світу після вивчення багатьох матеріалів підтвердили що першою хлібною рослиною треба вважати не жито і пшеницю а дуб.
82221. Еврика! Інтелектуальна гра у 10-11 класах 43 KB
  Як називається число при якому значення многочленна дорівнює нулю Які квадратні рівняння можна швидко розвязати за допомогою теореми Вієта Назвіть відомі Вам способи розвязування систем лінійних рівнянь Як називається графік квадратичної функції Коли дріб дорівнює нулю...
82222. Інтелект-шоу «ЕОМ – Еврика» 4.78 MB
  Головна мета нашого інтелект-шоу – розвинути пізнавальну діяльність учнів у області інформатики та інших предметів, знання яких необхідні при вивченні предмету, надати учням можливість продемонструвати ці знання, свою ерудицію та захоплення.