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) дополнительной памяти (если дерево организовывать так, как показано выше).

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

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

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

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

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


 

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

65104. РАСПРОСТРАНЕНИЕ ИСЛАМА В ЗОЛОТОЙ ОРДЕ (НА МАТЕРИАЛАХ ПОГРЕБАЛЬНЫХ ПАМЯТНИКОВ) 2.13 MB
  Халикова также разбирает проблему идентификации исламских погребений и делает попытку выделить типично мусульманские признаки в погребальном обряде опираясь на предписанные шариатом правила и на анализ археологических материалов...
65105. К ВОПРОСУ О РОЛИ СУФИЗМА В ИСЛАМИЗАЦИИ ЗОЛОТОЙ ОРДЫ 71 KB
  Однако проникновение ислама в Золотую Орду началось намного раньше ещё с момента её образования поэтому связывать исламизацию лишь с волевыми решениями ханской администрации было бы ошибочно.
65106. ГОРОДИЩЕ АК-САРАЙ 43.5 KB
  На восток охранная зона памятника включающая городище и мавзолеи протянулась на расстояние около 2250 метров от берега р. В природном отношении территория занимаемая городищем и комплексом мавзолеев представляет собой всхолмлённую слабозадернованную песчаную полупустыню.
65107. ИСЛАМ В ЗОЛОТОЙ ОРДЕ (ИСТОРИКО-АРХЕОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ) 4.28 MB
  С течением времени уменьшается число как богатых так и бедных погребений с признаками всадничества. Однако при соблюдении ряда основных признаков мусульманской погребальной обрядности по остальным признакам данные захоронения часто мало...
65109. Кыпчаки и Кимакский каганат. Йемеки 47 KB
  Легендарные сведения подтверждают указанное направление движения кыпчаков: согласно легенде о предке уйгуров Огузкагане последний послал кыпчаков чтобы они поселились между страной итбараков предположительно киргизов. Повидимому более раннее или параллельное название кыпчаков сиры.
65110. КНЯЗЬЯ КАЗАНСКИЕ, КНЯЗЬЯ БОЛГАРСКИЕ 103 KB
  Осенью этого года великий князь суздальский и нижегородский Дмитрий Константинович послал рать на Болгарского князя Асана вариант написания: Блъгарского князя Осана 4. высказана следующим образом: на Болгарского князя Асана еже ныне глаголются Казанцы выделено нами.
65111. Модель Татарстана: «За» И «Против» 134.5 KB
  Обычно Модель Татарстана противопоставляется опыту других регионов суверенизация которых была сопряжена с острыми кризисами Абхазия Чеченская республика Ичкерия и др. Но сам опыт Татарстана при этом рассматривается весьма однобоко в основном с точки зрения мирного характера...
65112. Об основных этапах становления татарской нации 248.5 KB
  Проблему формирования татарской нации на сегодня трудно считать изученной сколько-нибудь исчерпывающе. Ее автор выделил три основных этапа становления татарской буржуазной нации: первый с конца ХVII до конца ХVIII вв.