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

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

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

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

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

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


 

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

78703. Повреждения и заболевания конечностей 201.94 KB
  Стадия декомпенсации -– боли в покое изменения цвета кожи вынужденное положение конечности. Признаками перелома кости являются боль отечность тканей патологическая подвижность и крепитация костных отломков нарушение функции при возникновении смещения отломков деформация конечности.
78704. Социальная стратификация 152.5 KB
  Постоянное ранжирование социальных статусов и ролей в социальной системе. Социологи называют социальной стратификацией расположение индивидов и групп сверху вниз по горизонтальным слоям или стратам по признаку неравенства в доходах уровне образования объеме власти профессиональном престиже.
78706. В.А. Сухомлинский. Вклад в развитие педагогической науки 39.4 KB
  Сначала Сухомлинский подался было в медицинский техникум но вскоре ушел оттуда поступил на рабфак досрочно закончил его и был принят в педагогический институт. На дневном отделении учился Сухомлинский всего два года в 1935 г.
78707. Технологии политической агитации (политическая реклама, пропаганда, связи с общественностью) 58.5 KB
  Технологии политической агитации довольно разнообразны и их выбор диктуется определенными условиями как то: личность политического лидера условия региона и т. Технологии политической агитации относятся к видам деятельности которые требуют высочайшей компетенции персонала и их руководителей.
78708. Права и обязанности учеников в школе 38.99 KB
  Какие права связаны с правом на образование Право на образование следует рассматривать как совокупность прав: 1 на выбор образовательного учреждения или образовательной программы; 2 на получение образования в соответствии с установленными стандартами...
78710. История винограда и виноделия 140.5 KB
  Но постепенно с развитием знания явились новые факты: наряду с легендами природа открыла интересные страницы из которых люди смогли прочесть историю винограда в виде отпечатка виноградного листа.