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

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

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

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

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

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


 

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

69957. ВЫЯВЛЕНИЕ СФОРМИРОВАННОСТИ ОБРАЗОВ ИСТОРИЧЕСКОГО ПРОШЛОГО 754.5 KB
  Рассматривается дидактическая целесообразность применения категории образы исторических событий. Приводится пример комплекса разноуровневых заданий и их образец ориентированные на выявление уровня сформированности у учащихся образов исторических событий как...
69958. СОЦИАЛЬНЫЕ ПРЕДСТАВЛЕНИЯ БУДУЩИХ ПЕДАГОГОВ О ПСИХОЛОГИЧЕСКОМ НАСИЛИИ 179 KB
  Анкета была направлена на изучение следующих аспектов знаний приобретенных студентами в рамках учебных дисциплин и в процессе самообразования: сущность формы признаки причины последствия и эффективность психологического насилия.
69959. КОМПЕТЕНЦИИ ПРОФЕССИОНАЛЬНО-ТВОРЧЕСКОГО РАЗВИТИЯ ЛИЧНОСТИ СПЕЦИАЛИСТА ВОЕННОГО ПРОФИЛЯ 73.5 KB
  В статье определены понятия специалист военного профиля профессионально-творческое развитие личности проанализирована система общих профессиональных творческих компетенций в подготовке специалиста. Выявлены компетенции профессионально-творческого развития личности специалиста военного профиля.
69960. СТИГМАТИЗАЦИЯ ДЕТЕЙ В ГРУППЕ ДОШКОЛЬНОГО ВОЗРАСТА 78.5 KB
  Данная статья посвящена рассмотрению феномена стигматизации среди детей в группе старшего дошкольного возраста. В данной статье рассматривается проблема стигматизации детей в дошкольной группе а также личностные черты стигматизирующих стигматизированных и наблюдателей.
69961. «Якоря карьеры» студентов заочного отделения Белорусского национального технического университета 68 KB
  В статье авторы раскрывают понятия «мотивация», «профессиональная мотивация», «карьера», их виды, структуру, рассматривают различные научные подходы в их изучении. Статья содержит подробное описание методики Э. Шейна «Якоря карьеры».
69962. МЕНТАЛЬНЫЕ ВОЗМОЖНОСТИ ДОШКОЛЬНИКОВ КАК УСЛОВИЕ ИХ СПОСОБНОСТИ К ПРАВДИВОМУ И НЕПРАВДИВОМУ ПОВЕДЕНИЮ 65.5 KB
  Так под поведением понимается такая протяженная во времени активность человека которая включает в себя инициативные обращенные или ответные воздействия человека на любые воздействия других людей. Именно поведение человека отражает его представления о себе окружающем его мире...
69963. ВЛИЯНИЕ ПРОФЕССИОНАЛЬНЫХ ДЕСТРУКЦИЙ НА СТАНОВЛЕНИЕ ПРОФЕССИОНАЛЬНОЙ ИДЕНТИЧНОСТИ ПРЕПОДАВАТЕЛЯ ВУЗА 115.5 KB
  В статье рассматривается проблема влияния профессиональных деструкций на развитие профессиональной идентичности преподавателя высшей школы. Понятие идентичности под которой подразумевается твердо усвоенный и личностно принимаемый образ себя во всем богатстве...
69964. ФОРМИРОВАНИЕ ЭФФЕКТИВНОЙ ПЕДАГОГИЧЕСКОЙ ДЕЯТЕЛЬНОСТИ В ВУЗЕ ПОСРЕДСТВОМ ДИАЛОГИЧЕСКОГО ВЗАИМОДЕЙСТВИЯ 67 KB
  Однако несмотря на значительное количество исследований к настоящему времени еще не сложилась целостная концепция формирования межличностного диалогического взаимодействия в учебном процессе. Объясняется это не столько низким уровнем знаний информированности студентов...
69965. ВЕРБАЛЬНЫЙ ИНТЕЛЛЕКТ И ЧЕРТЫ ЛИЧНОСТИ СТУДЕНТА-ПСИХОЛОГА 43.13 KB
  В статье на основе парадигмы интеллекта как ментального опыта представлен анализ структуры вербального интеллекта и соотношения его факторов а также динамика функционирования вербального интеллекта в процессе формирования тематических и категориальных группировок.