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

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

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

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

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

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


 

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

27965. Краткая история проблемы мозговой локализации психических функций 26.04 KB
  Краткая история проблемы мозговой локализации психических функций. Центральная проблема нейропсихологии проблема локализации высших психических функций связана с решением вопроса о том какова мозговая география различных психических функций и как исследуя нарушения психических функций при повреждениях мозга установить их причину и локализацию в головном мозге. Такое определение позволяет сформулировать центральные вопросы нейропсихологии: 1 теоретический в соответствии с какими принципами и как размещаются в мозге человека...
27966. Рефлекс и реактивное поведение. Трехфакторная модель «значимого другого»: основные положения и методическое обеспечение 22.96 KB
  Важно чтобы мозг животного был свободен от других видов деятельности то есть его не должна отвлекать какаято посторонняя потребность и находиться на определенном уровне возбуждения На фоне различных видов тороможения или отвлекающих факторов обучение происходит медленно или не происходит вовсе. Кооперация необходимый элемент совместной деятельности порожденный ее особой природой. Леонтьев называл две основные черты совместной деятельности: разделение единого процесса деятельности между участниками; изменение деятельности...
27967. Предметный образ и его семантическая многоуровневость 84.99 KB
  Поскольку состояние контактного взаимодействия анализатора с раздражителем непосредственно заключающее в себе ввиду своей двусторонности основу предметного изображения имеет место именно в осязании и прежде всего в тактильных ощущениях постольку простейший предметный образ формируется как рефлекторный эффект деятельности кожномеханического анализатора. На высших уровнях осязательной репрезентации состояние взаимодействия рецептора с раздражителем осуществляется и поддерживается на основе активной деятельности руки как специфического...
27968. Психофизическая зависимость и психофизическая функция 40.9 KB
  Типы и способы межличностоной и межгрупповой коммуникации. Типы и способы межличностоной и межгрупповой коммуникации. Когда говорят о коммуникации в узком смысле слова то прежде всего имеют в виду тот факт что в ходе совместной деятельности люди обмениваются между собой различными представлениями идеями интересами настроениями чувствами установками и пр. Все это можно рассматривать как информацию и тогда сам процесс коммуникации может быть понят как процесс обмена информацией.
27969. Восприятие пространства и удаленности; монокулярные и бинокулярные признаки глубины 30.95 KB
  Восприятие пространства и удаленности; монокулярные и бинокулярные признаки глубины Чувственное отражение субъективный познавательный процесс и результат этого процесса где объективное познание выступает в виде чувственной формы а именно в виде ощущений восприятий и представлений компоненты чувственного отражения. Восприятие 1 субъективный образ предмета явления или процесса непосредственно воздействующего на анализатор или систему анализаторов перцептивный образ или образ восприятия 2 процесс формирования образа предмета или...
27970. Восприятие как процесс категоризации в трудах Дж. Брунера 36.92 KB
  Личность и психика развитие личности и развитие психики: соотношение понятий. Личность и психика развитие личности и развитие психики: соотношение понятий. Понятие личности обозначает человеческого индивида как члена общества обобщает интегрированные в нем социально значимые черты. Петровский Ярошевский Развитие личности процесс качественных психологических личностных изменений в личности а также результат этих изменений.
27971. Память как высшая психическая функция 23.01 KB
  Психология этнической социализации и этнической идентичности. Психология этнической социализации и этнической идентичности. Этническая социализация выполняет функцию формирования множественной и многоуровневой идентичности личности способствующей конструктивному функционированию этничности в жизни индивида и общества: позитивной этнической идентичности и толерантного этнического взаимодействия. Одним из основных институтов этнической социализации является семья.
27972. Эффект Зейгарник. Этническая идентичность: общее описание, структура, становление и формирование, изменения этнической идентичности 18.62 KB
  Механизмы и эффекты межличностного восприятия Этническая идентичность: общее описание структура становление и формирование изменения этнической идентичности. Эффект Зейгарник. Эффект незавершенного действия эффект Зейгарник явление характеризующее влияние на процессы памяти перерывов в деятельности.
27973. Долговременная, кратковременная, оперативная и иконическая память 27.68 KB
  Социальнопсихологический тренинг как средство повышения точности межличностного восприятия Особенности межкультурной коммуникации развитие культурной сензитивности. Непосредственный отпечаток полезен в тех случаях когда сигнал действует очень недолго как при просмотре к ф; он обеспечивает также непрерывность восприятия при моргании или движении глаз. Социальнопсихологический тренинг как средство повышения точности межличностного восприятия В процессе общения должно присутствовать взаимопонимание между участниками этого процесса....