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

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

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

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

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

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


 

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

69226. Графічний метод зображення статистичних даних 334.5 KB
  Вимоги до статистичного графіка та його основні елементи. Слід нагадати що побудова графіка виправдана якщо він дає будьякі переваги порівняно з цифрами які зведені в ряди або таблиці. Основні елементи графіка.
69227. Статистичне зведення та групування 188 KB
  Значення коефіцієнтів наведено в таблиці. Статистичні таблиці їх значення в статистиці види таблиць. Статистичні таблиці призначені для найбільш раціонального наочного та систематизованого викладення результатів зведення і групування статистичних даних.
69228. Індекси. Суть індексів, їх особливості як узагальнюючих показників 143.5 KB
  Термін індекс (іпdех) є синонімом певної узагальнюючої характеристики. Наприклад, індекс реальних доходів населення за рік, індекс курсової вартості цінних паперів за місяць, регіональний індекс злочинності тощо. Кожний індекс є співвідношенням двох значень показника...
69229. Історія формування та розвитку статистики. Статистика у феодальному суспільстві та в епоху відродження. Розповсюдження товарно–грошових відносин та розвиток статистики 74 KB
  Історія вітчизняної соціально-економічної статистики Розвиток державної статистики визначається багатьма умовами і чинниками економічного соціального організаційного характеру. Становлення державної статистики можна віднести до кінця XVII початку XVIII в.
69230. Організація державної статистики в Україні та її структура 128 KB
  Цей Закон регулює правові відносини в галузі статистики і ведення первинного обліку визначає повноваження та функції органів державної статистики і створює основу для ведення державної інформаційної системи України з метою одержання достовірної статистичної інформації...
69231. Організація міжнародної статистики 155.5 KB
  Таким чином послідовна розробка міжнародних рекомендацій в області статистики дозволила МСІ закласти наукові основи міжнародних класифікацій по найважливіших розділах статистики і їх застосуванні але вже опосередковано через діяльність Ліги Націй і через ООН...
69232. Статистика продуктивності праці 120 KB
  Статистика продуктивності праці. Поняття продуктивності праці та завдання її статистичного вивчення. Показники рівня продуктивності праці та методи їх обчислення. Індексний метод у вивченні динаміки продуктивності праці.
69233. Робота з масивами і матрицями 86.72 KB
  При роботі з таблицями часто виникає ситуація, коли необхідно використати одну й ту ж операцію або формулу до деякого діапазону комірок, які утворюють інтервал масиву (масив-інтервал). MS Excel надає різні засоби для розв’язку такого типу задач.