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

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

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

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

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

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


 

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

18075. АНТЕНИ СИСТЕМ СУПУТНИКОВОГО РАДІОЗВ’ЯЗКУ 1.3 MB
  ЛЕКЦІЯ №2 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 1: АНТЕНИ РТС ПЕРЕДАЧІ ІНФОРМАЦІЇ. ЗАНЯТТЯ 2: антенИ систем супутникового радіозвязку 1. НАВЧАЛЬНІ ПИТАННЯ Вимоги до антен системи супутникового ра
18076. АНТЕНИ РАДІОРЕЛЕЙНИХ ЛІНІЙ 284 KB
  ЛЕКЦІЯ №3 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 1: АНТЕНИ РТС ПЕРЕДАЧІ ІНФОРМАЦІЇ. ЗАНЯТТЯ 4: антенИ радіоРЕЛЕЙНИХ ЛІНІЙ 1. НАВЧАЛЬНІ ПИТАННЯ Вимоги до антен радіорелейних ліній. 2. Особли
18077. АНТЕНИ СИСТЕМ КОРОТКОХВИЛЬОВОГО ЗВ’ЯЗКУ ТА РАДІОМОВЛЕННЯ 258.5 KB
  ЛЕКЦІЯ №4 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 1: АНТЕНИ РТС ПЕРЕДАЧІ ІНФОРМАЦІЇ. ЗАНЯТТЯ 5: антенИ систем короткохвильового звязку та радіомовлення. 1. НАВЧАЛЬНІ ПИТАННЯ Вимоги до антен коротк...
18078. ЧАСТОТНО НЕЗАЛЕЖНІ АНТЕНИ 365.5 KB
  ЛЕКЦІЯ №5 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 2: Частотні властивості антен. ЗАНЯТТЯ 1: Частотно незалежні антени 1. НАВЧАЛЬНІ ПИТАННЯ Принцип створення частотно незалежних антен. 2. Пр
18079. АКТИВНІ ПЕРЕДАВАЛЬНІ АНТЕНИ 351 KB
  ЛЕКЦІЯ №7 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 3: Активні антени. ЗАНЯТТЯ 1: Активні передавальні антени. 1. НАВЧАЛЬНІ ПИТАННЯ Загальні відомості про активні передавальні антени. Ант...
18080. АКТИВНІ ПРИЙМАЛЬНІ АНТЕНИ 408.5 KB
  PAGE 32 ЛЕКЦІЯ №8 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ для студентів 5 курсу ТЕМА 3: Активні антени. ЗАНЯТТЯ 2: Активні прИЙМАльні антени. 1. НАВЧАЛЬНІ ПИТАННЯ Загальні відомості про активні приймальні ан...
18081. АНТЕНИ ТА ЕЛЕКТРОМАГНІТНА СУМІСНІСТЬ (ЕМС) 384 KB
  ЛЕКЦІЯ №10 з навчальної дисципліни ПРИКЛАДНІ ПИТАННЯ АНТЕННИХ ПРИСТРОЇВ ТЕМА 4: Антени та ЕМС. Моделювання та проектування антеннофідерних пристроїв ЗАНЯТТЯ 1: Антени та електромагнітна сумісність ЕМС 1. НАВЧАЛЬНІ ПИТАННЯ ...
18082. Работа со строками в Java 311.5 KB
  Лабораторная работа 5 Работа со строками в Java. Цель работы Целью работы является приобретение навыков программирования с использованием строк языка Java. Состав рабочего места. Оборудование: IBMсовместимый персональный компьютер ПК. Программное...
18083. Программирование апплетов в Java 364 KB
  Лабораторная работа 303 Программирование апплетов в Java 1. Цель работы Целью работы является приобретение навыков программирования апплетов Java с использованием средств AWT. 2. Состав рабочего места 2.1. Оборудование: IBMсовместимый персональный компьютер ПК. ...