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

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

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

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

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

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


 

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

56423. Модели комбинаторики сниженной стилистической маркированности слов на примере произведений Сью Таунсенд «The Secret Diary of Adrian Mole, Aged 13¾» «The Growing Pains of Adrian Mole» и «The True Confessions of Adrian Albert Mole» 549 KB
  Объектом исследования данной работы являются слова сниженной стилистической маркированности, присущие художественному дискурсу С. Таунсенд.
56424. Інфінітивні групи. Тести. (10-11 класи) 102.5 KB
  Ich habe... meine Hausaufgaben zu machen. meine Hausaufgaben zu mache. zu machen meine Hausaufgaben.
56425. Проектирование ресторана «Атлантида» 1.33 MB
  В настоящее время общественное питание достигло огромного прогресса, который не останавливается, а продолжает развиваться все с большей и большей скоростью. Это доказывается появлением и открытием большого количества ресторанов и баров разного класса, кафе, столовых, всевозможных закусочных и других предприятий
56426. ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКАЯ ХАРАКТЕРИСТИКА СПК «ПОБЕДА» ЕРАВНИНСКОГО РАЙОНА 456.5 KB
  В последнее десятилетие произошли кардинальные изменения во многих сферах экономической деятельности, в том числе в системе оплаты труда и отчислений страховых взносов в социальные фонды.
56427. ДЕЯКІ ТАБЛИЦІ ТА АЛГОРИТМИ, ЯКІ ДОПОМАГАЮТЬ УЧНЯМ 36 KB
  Навчити учня вчитися, забезпечити його такою системою знань і умінь, які необхідні для подальшої самоосвіти, розвинути його творчу особистість повинна сьогодні школа. Вона не може дати людині запас знань на все життя...
56428. Внедрение информационных технологий в начальной школе - важный фактор развития способностей ребенка 32.5 KB
  Ведь с помощью компьютера можно получить увидеть или услышать определённую информацию: текст кроссворд картинку звук аудиозапись текстовый материал видеозапись просмотр любого развивающего...
56429. НАЙРОЗУМНІШИЙ 109 KB
  Питання охоплюють мовознавчий матеріал з тем Словосполучення та просте речення та Складносурядні та складнопідрядні речення оскільки бажано гру проводити під час тижня української мови...
56430. ПІДГОТОВКА ВЧИТЕЛЯ ДО РЕАЛІЗАЦІЇ ОЗДОРОВЧОЇ ФУНКЦІЇ ОСВІТИ 114 KB
  Актуальність статті передбачає пропаганду здорового способу життя дітей та молоді через проведення батьківських лекторіїв конференцій тренінгів круглих столів лекцій практичних занять для батьків та учнівської молоді.
56431. КРЕВСЬКА УНІЯ ТА СПРОБИ ЇЇ РЕАЛІЗАЦІЇ НА УКРАЇНСЬКИХ ЗЕМЛЯХ 311.5 KB
  Колишня київська Русь могла сплачувати щедру данину, мала розгалужені торговельні шляхи була спроможна надати Литві матеріальні ресурси і поповнення до війська. Не останню роль відігравав і династичний чинник - правляча литовська династія мала численних нащадків, що потребували власних уділів.