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

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

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

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

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

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


 

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

5818. Роль банковской системы в государственной деятельности 82 KB
  В настоящее время изучение банковской системы является одним из актуальных вопросов российской экономики. Очень многие современные бизнесмены посвятили себя теме изучения и анализа функционирования банков в России и создания наилучших услов...
5819. Бизнес-план инновационного предприятия 439.5 KB
  Описание продукции Товар Электроудочка - это такое устройство, при помощи которого можно ловить рыбу в больших количествах, и очень быстро. Идея электроудочки основана на том, что при протекании в воде постоянного тока, возникает так называем...
5820. Политическая система 71.5 KB
  Политическая система План: Понятие политической системы История проблемы. Структура политических систем Типы политических систем. 5) Функции политических систем. Понятие политической системы Под политической систе...
5821. Бюджет и бюджетная система Российской Федерации 549 KB
  Объектом дипломной работы является бюджетная система и проблемы исполнения бюджетов разных уровней в РФ. Актуальность выбранной для исследования темы заключается в первостепенной важности бюджета для функционирования национальной экономики,...
5822. Подбор оборудования 143.5 KB
  Подбор одноступенчатого компрессора. Задание Задача расчета Произвести подбор одноступенчатого компрессора и проанализировать проектные варианты. ИСХОДНЫЕ ДАННЫЕ. Эскиз внешнего вида и планировка сборной камеры представлены на р...
5823. Сущность денег и финансовые институты 986.5 KB
  Введение Тема курсовой работы представляет интерес для меня тем, что деньги и банки в совокупности образуют одну из самых важных и притягательных областей экономики. Деньги и банки являются неотъемлемыми атрибутами современной цивилизации. Их изучен...
5824. Внутренний аудит организации безопасности полетов в авиа-компании 74 KB
  Внутренний аудит организации безопасности полетов в авиакомпании Честная и критичная самооценка является одним из наиболее эффективных способов определения уровнем безопасности полетов в авиакомпании. Всемирный фонд авиационной безопасности разработ...
5825. Управление и автоматизированные системы управления строительством 5.73 MB
  АСУ является частным случаем системы управления (СУ) соответствующего уровня, в которой, помимо двух понятий «система» и «управление», синтезируется понятие автоматизации управленческих функций и процессов, перечисленных выше.
5826. Создании несложной игровой программы Морской бой 1.97 MB
  Введение ИГРА-вид непродуктивной деятельности,мотив которой заключается не в ее результатах,а в самом процессе.В истории человеческого общества переплеталась с магией,культовым поведением и др. Свойс...