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

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

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

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

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

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


 

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

30072. Метод Рунге-Кутта 4-го порядка. Решение обыкновенных дифференциальных уравнений 323.5 KB
  Многие физические законы, которым подчиняются те или иные явления, записываются в виде математического уравнения, выражающего определенную зависимость между какими-то величинами. Большое значение, которые имеют дифференциальные уравнения для математики и особенно для ее приложений, объясняется тем, что к решению таких уравнений сводится исследование многих физических и технических задач.
30073. Оценка конкурентоспособности товара и разработка стратегии маркетинга предприятия 1.35 MB
  Выпуск конкурентоспособного товара и его реализация, позволяют ему возмещать производственные затраты. Достижение конкурентоспособности своей продукции и увеличение объема ее реализации является важной задачей для каждого предприятия. Для этого каждая фирма следует той или иной стратегии маркетинга, пригодной для товара определенного жизненного цикла.
30074. Визуализация численных методов. Решение дифференциального уравнения 1-го порядка 1.2 MB
  Существует множество технических систем и технологических процессов, характеристики которых непрерывно меняются с течением времени. Такие явления обычно подчиняются физическим законам, которые формулируются в виде дифференциальных уравнений. И поэтому умение решать дифференциальные уравнения является необходимым фактором, для того чтобы наиболее полно понимать окружающий мир и процессы, происходящие в нём.
30077. Розрахунок і аналіз перехідних процесів у електроприводі системи генератор-двигун 502.89 KB
  За вихідними даними необхідно: виконати вибір генератора постійного струму ГПС та його привідного асинхронного двигуна АД; розрахувати та побудувати статичні характеристики ЕП визначити робочі точки на механічних характеристиках і на характеристиках намагнічування; визначити динамічні параметри ЕП; розрахувати коефіцієнт форсування збудження генератора; розрахувати опір резисторів у колі обмотки збудження генератора; виконати розрахунок перехідних процесів у колі збудження генератора та якірному колі системи ГД графоаналітичним...
30078. Расчет источника питания 396 KB
  Источник питания состоит из силового трансформатора, выпрямителей, сглаживающих фильтров и во многих случаях – стабилизаторов напряжения (или тока). Расчет начнём с конечного элемента – со стабилизатора, а затем рассчитаем трансформатор.
30079. ТРАНСФОРМАТОР ТМ – 630/10 1.46 MB
  1 Расчет винтовой обмотки 18 3.1 Расчет многослойной цилиндрической обмотки 23 из провода круглого сечения 4 Расчет параметров короткого замыкания 27 4.2 где UH номинальное линейное напряжение обмотки кВ SH в кВА.8 кВА Классом напряжения трансформатора считают класс напряжения обмотки ВН.
30080. Общая психология: Учебник для вузов 6.29 MB
  Павлова 82 Исследования функциональной асимметрии мозга 112 Теория научения 128 Теории слуха 192 Теории цветового зрения 196 Феноменальная память 280 Патология воли 381 Это интересно Что является механизмами сознания 96 Существует ли явление пси 154 Как происходит передача информации от рецептора в мозг 166 Как человек распознает объект ы 204 Что позволяет человеку адекватно воспринимать окружающий мир 226 Можно ли изучать представления 237 Как происходит кодирование и сохранение информации в памяти 256 Амнезия детства...