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

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

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

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

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

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


 

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

16348. ОПРЕДЕЛЕНИЕ ЕМКОСТИ КОНДЕНСАТОРА 1.27 MB
  ЦЕЛЬ РАБОТЫ: знакомство с одним из методов измерения электрической емкости конденсатора; экспериментальная проверка формул для расчета емкости батареи конденсаторов при их параллельном и последовательном соединениях. ОБОРУДОВАНИЕ Регулируемый источн...
16349. ИССЛЕДОВАНИЕ ИНДУКЦИОННОГО РЕГУЛЯТОРА И ФАЗОРЕГУЛЯТОРА 192.5 KB
  ИССЛЕДОВАНИЕ ИНДУКЦИОННОГО РЕГУЛЯТОРА И ФАЗОРЕГУЛЯТОРА 1. Цель работы 1.1. Изучить работу асинхронной машины с фазным ротором в режиме индукционного регулятора и фазорегулятора. 1.2. Ознакомиться с принципиальными схемами индукционного регулятора и фазорегулятор
16350. ИССЛЕДОВАНИЕ ОДНОФАЗНОГО АСИНХРОННОГО ДВИГАТЕЛЯ 66 KB
  ИССЛЕДОВАНИЕ ОДНОФАЗНОГО АСИНХРОННОГО ДВИГАТЕЛЯ 1. ЦЕЛЬ РАБОТЫ. 1.1.Ознакомиться с конструкцией принципом действия и режимами работы однофазных асинхронных двигателей. 1.2.Приобрести практические навыки в определении параметров и исследовании р...
16351. ИЗУЧЕНИЕ И ИССЛЕДОВАНИЕ СВОЙСТВ АСИНХРОННОГО ДВИГАТЕЛЯ С КОРОТКОЗАМКНУТЫМ РОТОРОМ 103.12 KB
  ИЗУЧЕНИЕ И ИССЛЕДОВАНИЕ СВОЙСТВ АСИНХРОННОГО ДВИГАТЕЛЯ С КОРОТКОЗАМКНУТЫМ РОТОРОМ 1. Цель работы 1.1. Ознакомление с конструкцией трехфазного асинхронного двигателя с короткозамкнутым ротором. 1.2. Проведение опытов холостого хода короткого замы
16352. ИСПЫТАНИЕ АСИНХРОННОГО ДВИГАТЕЛЯ С ФАЗНЫМ РОТОРОМ 200 KB
  ИСПЫТАНИЕ АСИНХРОННОГО ДВИГАТЕЛЯ С ФАЗНЫМ РОТОРОМ ЦЕЛЬ РАБОТЫ 1.1. Ознакомиться на разобранном образце по учебнику и конспекту лекций с конструкцией асинхронного двигателя с фазным ротором. 1.2. Получить практические навыки пуска асинхронного двигателя с ...
16353. РАБОТА СИНХРОННОГО ГЕНЕРАТОРА НА ИНДИВИДУАЛЬНУЮ НАГРУЗКУ 280 KB
  РАБОТА СИНХРОННОГО ГЕНЕРАТОРА НА ИНДИВИДУАЛЬНУЮ НАГРУЗКУ ЦЕЛЬ РАБОТЫ Ознакомиться по учебнику и конспекту лекций с конструкцией основных видов синхронных машин. Приобрести практические навыки в исследовании синхронных машин. П...
16354. ИСПЫТАНИЕ АСИНХРОННОЙ МАШИНЫ В РЕЖИМЕ ГЕНЕРАТОРА 318 KB
  ИСПЫТАНИЕ АСИНХРОННОЙ МАШИНЫ В РЕЖИМЕ ГЕНЕРАТОРА. ЦЕЛЬ РАБОТЫ. Ознакомиться на разобранном образце по учебнику и конспекту лекций с конструкцией асинхронной машины. Получить практические навыки перевода асинхронной машины из двигател...
16355. Исследование параметров микроклимата 404 KB
  Исследование параметров микроклимата Методические указания к выполнению лабораторной работы по курсу Безопасность жизнедеятельности для студентов очного и заочного обучения всех направлений и специальностей Безопасность жизнедеятельности. Методические указ
16356. Контроль состояния изоляции проводов 99.5 KB
  Контроль состояния изоляции проводов Методические указания к выполнению лабораторной работы по курсу Безопасность жизнедеятельности для студентов очного и заочного обучения всех направлений и специальностей Безопасность жизнедеятельности. Методические ука...