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

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

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

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

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

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


 

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

44057. Повышение социальной компетентности подростков 15-16 лет, выпускников детских домов, средствами социально-культурной деятельности 1.04 MB
  Теоретические основы формирования социальной компетентности подростков выпускников детских домов с помощью средств социально-культурной деятельности Сущность и определение социальной компетентности. Особенности процесса формирования социальной компетентности у подростков.
44058. Проектування дорожнього СТО-А 370 KB
  Автомобілі на станції технічного обслуговування СТО приймаються відповідно до встановлених правил. Значний ріст парку легкових автомобілів що належать населенню в Україні вимагає збільшення проектування дорожніх СТОА. Виробничотехнічну базу системи технічного обслуговування автомобілів в основному складають підприємства структурні одиниці трьох видів: СТОА у тому числі майстерні і пункти ТО і ремонту; бази і склади матеріальнотехнічного постачання; гаражі і стоянки автомобілів. Сучасні СТОА здійснюють: продаж і...
44059. Разработка бизнес-плана по производству кондитерских изделий ООО «Бансес» 251.5 KB
  Важнейшей задачей разработки бизнеспланов является проблема привлечения и обоснования инвестиций и кредитов в том числе зарубежных необходимых для осуществления проектов технического перевооружения и реконструкции предприятий. 1337580 руб. 5788080 руб. Общая стоимость проекта по производству кондитерских изделий 936671 руб.
44060. Психологізм творчості Михайла Коцюбинського 475 KB
  Зображення процесів внутрішнього життя героїв у дитячих оповіданнях письменника За обєкт дослідження обрано дитячу та малу прозу Михайла Коцюбинського Цвіт яблуні Сон Що записано в книгу життя В дорозі Дорогою ціною Дебют Лялечка Ft morgn Харитя Ялинка Маленький грішник Intermezzo як найпоказовішу з погляду психологічного зображення зрілості авторської концепції. Із метою ширшого обґрунтування останньої комплексного розгляду художнього психологізму залучено інформацію про особисте життя...
44061. Расчет преобразовательного агрегата 2.27 MB
  Совместно с американскими специалистами были проанализированы достоинства и недостатки электроэнергетики России и США. Специалисты отрасли умели управлять ЕЭС и знали как её оптимально приспособить к рынку.
44062. Податковий контроль 290 KB
  Визначення поняття методика податкового контролю Податковий контроль властивий будь якій державі. Податковий контроль як один із елементів державного регулювання особливо в умовах нестабільної економічної ситуації має стати обєктивною передумовою подальшого розвитку підприємств сприяти удосконаленню податкового механізму через вияв економіко організаційного механізму оподаткування. У здійсненні податкового процесу чільне місце посідає саме контроль за формуванням і практичною реалізацією системи оподаткування в...
44063. Вплив соціально-психологічних факторів на мотивації поведінки неформальної молоді 588.5 KB
  В даній роботі виконано завдання щодо виявлення на основі тестування впливу соціальнопсихологічних факторів на мотивації поведінки неформальної молоді. Обєкт дослідження поведінка неформальної молоді Предмет дослідження вплив соціально-психологічних факторів на мотивації поведінки неформальної молоді Мета дослідження виявити соціальнопсихологічні фактори що впливають на мотивацію поведінки неформ молоді Завдання дослідження: аналіз сучасних досліджень впливу соцпсихол фактор на мотивац повед неформальн молодівизначення...
44064. Конкурентоспособность торговой организации ООО «Первая компьютерная компания» 727 KB
  Организационно-экономическая характеристика предприятия Оценка конкурентоспособности предприятия Предмет исследования конкурентоспособность торгового предприятия. Исходя из поставленных целей можно сформировать следующие задачи: исследование теоретических и методологических основ оценки конкурентоспособности фирмы; обоснование комплексного подхода к обеспечению конкурентоспособности товара; анализ деятельности сети магазинов Первая компьютерная компания; разработка мероприятий по повышению...
44065. АНАЛИЗ БУХГАЛТЕРСКОЙ ОТЧЕТНОСТИ И ФИНАНСОВЫХ РЕЗУЛЬТАТОВ ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТИ 629 KB
  Анализ финансовых результатов деятельности предприятия Оценка имущественного положения предприятия Оценка ликвидности и платежеспособности вероятности банкротства предприятия Анализ деловой активности и рентабельности предприятия ООО Компания Альянс.