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

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

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

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

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

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


 

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

65548. МЕТОДИ ТА СИСТЕМИ ВІДТВОРЕННЯ ЗОБРАЖЕНЬ НА БАЗІ ЛОГІКО-ЧАСОВИХ ПЕРЕТВОРЕННЬ 857.65 KB
  Для візуального подання інформації та її реалістичного відображення необхідно створити системи відтворення зображень серед яких перспективними є світлодіодні матричні екрани які широко використовуються в професійних інсталяціях.
65549. ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ОБРОБКИ НА СЕРЕДНІХ ТОКАРНИХ ВЕРСТАТАХ ЗА РАХУНОК ОПТИМІЗАЦІЇ КОНСТРУКТИВНИХ ПАРАМЕТРІВ РІЗЦІВ І РЕЖИМІВ РІЗАННЯ 868.5 KB
  В умовах ринкової економіки вибір типа конструкції інструменту його параметрів режимів різання має бути кількісно обґрунтований з урахуванням багатьох технічних економічних і ергономічних факторів причому рішення що приймаються мають бути оптимальними.
65550. ТЕХНОЛОГІЯ СТРУКТУРНИХ МОДИФІКАЦІЙ ДЕГРАДАЦІЙНО-РЕЛАКСАЦІЙНИХ ПЕРЕТВОРЕНЬ В ФУНКЦІОНАЛЬНИХ МАТЕРІАЛАХ НА ОСНОВІ СТЕКОЛ ТА КЕРАМІКИ ДЛЯ СЕНСОРІВ ЕЛЕКТРОННОЇ ТЕХНІКИ 376.5 KB
  Визначальним фактором прогресу сучасного людського суспільства є розвиток матеріалознавства, пошук, розробка та широке впровадження принципово нових та синтетичних матеріалів з унікальними функціональними властивостями, високою надійністю і технологічною відтворюваністю.
65551. ІНВЕСТИЦІЙНА ПРИВАБЛИВІСТЬ СІЛЬСЬКОГОСПОДАРСЬКИХ ПІДПРИЄМСТВ 223 KB
  Тому одним із найважливіших завдань які стоять перед кожним з них зокрема та перед економікою країни в цілому є підвищення рівня інвестиційної привабливості. Особливої гостроти проблема підвищення інвестиційної привабливості набуває в сільському господарстві яке значно відстало...
65552. ПІДВИЩЕННЯ ТОЧНОСТІ ВИМІРЮВАННЯ ТЕМПЕРАТУРИ ТЕРМОПАРАМИ В ПРОЦЕСІ ЕКСПЛУАТАЦІЇ 1.36 MB
  Метою дисертації є розробка методу корекції похибки від набутої в процесі тривалої експлуатації термоелектричної неоднорідності електродів термопар на основі аналізу властивостей цієї похибки.
65553. ОРГАНІЗАЦІЙНО-ПЕДАГОГІЧНІ УМОВИ ПРОФЕСІЙНОЇ ПІДГОТОВКИ ФАХІВЦІВ ПОЖЕЖНО-РЯТУВАЛЬНОЇ СЛУЖБИ 295.64 KB
  Водночас важливим шляхом у процесі трансформування є глибоке осмислення й усвідомлення власного історичного досвіду звернення до національних джерел зародження і розвитку професійної підготовки фахівців пожежнорятувальної служби.
65554. Комплексна оцінка успішності інтродукції видів роду PICEA Dietr. в умовах Сходу України 317 KB
  На Сході України ялини є інтродукованими видами. Уперше для умов Сходу України: визначено особливості росту якісні показники селекційну структуру стан формове різноманіття та репродуктивну спроможність ялин; визначено перспективність застосування видів ялин для створення насаджень...
65555. УДОСКОНАЛЕННЯ АНАЛОГО-ЦИФРОВОЇ СИСТЕМИ СИНХРОННОГО СТЕРЕОФОНІЧНОГО РАДІОМОВЛЕННЯ З ПІЛОТ-ТОНОМ 467.5 KB
  Стереофонічний ефект і його якість є основою системи стереофонічного радіомовлення, тому має місце нагальна необхідність проведення подальших досліджень з встановлення необхідних захисних відношень за радіочастотою, що забезпечували би високу якість стереофонічного радіоприймання.
65556. Експериментально–розрахунковий аналіз деформацій циліндричних оболонок в зоні удару 1.99 MB
  Циліндричні оболонки можуть служити моделлю для ряду елементів конструкцій на які діють ударні навантаження. При розробці математичної моделі напружено–-деформованого стану було використано систему рівнянь коливання оболонки типу С.