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

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

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

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

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

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


 

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

1099. Дизайн комп’ютерної графіки та реклами 592 KB
  Основними завданням випускної роботи освітньо-кваліфікаційного рівня Спеціаліст. Вимоги до оформлення та представлення на захист випускної роботи. Стандартне вирішення оформлення першого планшету. Проектні об’єкти комплексної розробки рекламних виробів.
1100. Операционная система DOS 35 KB
  Установка операционной системы DOS, изучение основных команд и программ обслуживание.
1101. Операционная система Windows 98 Second Edition (9X) 40 KB
  На этой лабораторной работе Вы установите операционную систему Windows 98 Second Edition, научитесь основным программам обслуживания, работе с реестром и методам восстановления реестра. Воспользуйтесь ранее установленной виртуальной машиной с операционной системой DOS. Укажите в настройках виртуальной машины CD - ISO образ и выберите местонахождение образа.
1102. Операционные системы Windows 2003 Server и Windows XP Professional 223.5 KB
  Вы научитесь устанавливать операционную систему Windows XP Professional, создавать и работать с консолями, настраивать и пользоваться удаленным подключением к рабочему столу. Вы также настроите компьютер для работы под управлением Windows Server 2003.
1103. Операционные системы UNIX на примере реализации Kubuntu 52 KB
  Запуск операционной системы Kubuntu Desktop 6 (Portable). Навигация в linux. Создание и модификация пользователей и групп. Установка и удаление программ на примере пакета webmin. Просмотр системной информации. Манипулирование владельцами файлов и директорий.
1104. Организация рабочей среды пользователя 2.95 MB
  Посмотрите, какие существуют варианты настройки меню Пуск и Панели задач. Создать локальную группу созданных пользователей. Проделать это двумя способами: через окно свойств группы и окно свойств пользователя. Демонстрация работоспособности основных команд встроенного интерпретатора команд системы. Для одного из пользователей сделать сценарий входа.
1105. Вивчення технології роботи з СУБД Access 1.19 MB
  Для роботи з Access на локальному комп'ютері користувача має бути встановлена операційна система Windows 95 (98, NT) і СУБД Access. Щоб почати роботи з СУБД Access, необхідно після завантаження операційної системи запустити Access.
1106. Преобразователи электрических сигналов на операционных усилителях 787 KB
  Исследование следующих схем на ОУ: сумматор, схема сложения-вычитания, интегратор, дифференциатор, а также логарифмический усилитель с n–р–n-транзистором, включенным в цепь ООС ОУ.
1107. Методы и приборы контроля качества и диагностики состояния объектов 620 KB
  Поверка аналоговых электроизмерительных средств. Расширение пределов измерения аналоговых электроизмерительных приборов. Измерение активных и реактивных сопротивлений косвенным методом. Измерение напряжений и токов при помощи электронного осциллографа.