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

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

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

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

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

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


 

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

30947. Червячные передачи 287 KB
  Обычно червячная передача состоит из червяка 1 и сопряженного с ним червячного колеса 2. Червячная передача также как и винтовая характеризуется относительно высокими скоростями скольжения витков червяка по зубьям червячного колеса. Недостатки червячных передач обусловлены большими скоростями скольжения витков червяка по зубьям червячного колеса а также значительными осевыми силами действующими на валах передачи. Классификация червячных передач: по направлению линии витка червяка правые при наблюдении с торца червяка и его вращении...
30948. Предмет психодиагностики. Цели задачи область применения психодиагностики 261 KB
  прогнозирование перспектив индивидуального развития и возможных отклонений от его закономерного хода. В зависимости от конкретного случая психодиагност проводит обследование потерпевших подозреваемых или свидетелей и формулирует психологическое заключение о тех или иных качествах личности уровне интеллектуального развития психофизиологических особенностях и т. Формулировка заключений например об уровне психического развития. Для его определения сопостався результаты тестя с уровнем развития измеряемого признака качества личности на...
30949. Лекарственные травы 983 KB
  Листья тройчатые с пильчатым краем. Смягчающие травы: листья алтея листья мальвы донник ромашка семя льна смешивают в равных количествах и растирают в грубый порошок для компрессов. Используемые части: плоды и листья. Аптечное наименование: плоды голубики Uliginosi fractus ранее: Fructus Uliginosi листья голубики Uliginosi folium ранее: Folia Uliginosi.
30950. Социальная педагогическая психология 3.16 MB
  Кроме того, следует помнить, что самим результатом профессионально-педагогической деятельности является развитие личности учащегося, характер которого, в свою очередь, влияет на методы воспитания, иллюстрируя принцип обратной связи в педагогическом процессе. На сегодняшний день можно считать доказанным, что обратная связь, посредством которой педагог анализирует результаты собственного труда, является необходимым условием роста профессионально-педагогического мастерства.
30951. Экология. Живая и неживая природа 30.05 KB
  Геоэкология изучает специфику взаимоотношений организмов и среды их существования в разных географических зонах дает экологическую характеристику разных географических регионов рассматривает последствия добычи полезных ископаемых занимается экологическим картографированием. Экологи́ческие фа́кторы свойства среды обитания оказывающие какоелибо воздействие на организм. Индифферентные элементы среды например инертные газы экологическими факторами не являются. οἶκος жилище местопребывание и σύστημα система биологическая система...
30952. Экономическая теория. Методы экономической науки 215.85 KB
  Общие экономические законы действуют при нескольких смежных стадиях общественного развития эпохах или нескольких способах производства. К таковым относят закон товарного производства спроса стоимости законы денежного обращения. Специфические экономические законы обслуживают только одну стадию общественного развития или только один способ производства например закон первоначального накопления капитала.Потребности как предпосылка производства.
30953. Основи економічної теорії 1.96 MB
  Це сфера суспільного виробництва або сфера економіки. Розв'язання цієї суперечності й зумовило інтерес людства до з'ясування закономірностей які регулюють сферу використання обмежених ресурсів тобто сферу суспільного виробництва. На противагу меркантилістам фізіократи вважали що багатство створюється не за рахунок обміну чи торгівлі а в результаті праці у сфері виробництва.
30954. ЭТОЛОГИЯ – НАУКА О ПОВЕДЕНИИ ЖИВОТНЫХ 87 KB
  Этология наука о поведении животных Таксисы Инстинкт Рефлекс Обучение Запечатление Условный рефлекс Инструментальный условный рефлекс Метод проб и ошибок Подражание Инсайт Мышление 2. Типы высшей нервной деятельности и поведение животных 4. Список литературы ЭТОЛОГИЯ НАУКА О ПОВЕДЕНИИ ЖИВОТНЫХ Термин этология происходит и греческого слова этос и означает поведение характер. Этология как наука о биологических закономерностях поведения значительное развитие...
30955. Социально инвестиционная программа «Пуховый мир» 848.5 KB
  Бизнес план социально инвестиционной программы Пуховый мир Муниципальное образование Верхнесалдинский район Возрождение старинного рукодельного ремесла в Свердловской области Проект Пуховый мир Социально инвестиционная программа Создания Уральского пухово шерстяного народно художественного промысла Автор и исполнитель: Мустакимов Вячеслав Алексеевич Общая стоимость проекта: 563007 USD Требуются инвестиции: 200000 USD Срок реализации: 5 лет Россия...