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

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

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

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

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

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


 

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

34068. Классификация, основания возникновения и прекращения земельных правоотношений 30 KB
  Классификация основания возникновения и прекращения земельных правоотношений. КЛАССИФИКАЦИЯ ЗЕМЕЛЬНЫХ ПРАВООТНОШЕНИЙ Существенные различия природных свойств земли и неодинаковость хозяйственного ее использования могут обусловливать самые разнообразные земельные отношения. Это позволяет говорить о классификации земельных отношений по основному хозяйственному назначению земель. Классификацию земельных правоотношений можно строить и по другим признакам в зависимости от того какую особенность земельных правоотношений мы намерены выделить...
34069. Управление в сфере использования и охраны земель 39 KB
  Управление в сфере использования и охраны земель. В основе государственного управления лежит право территориального верховенства государства которое позволяет с одной стороны осуществлять защиту земельных прав и оказывать содействие физическим и юридическим лицам в реализации земельных прав напр. любое лицо может получить выписку из земельного кадастра с другой стороны это право позволяет привлекать виновных лиц к ответственности и выявлять в целом нарушения земельного законодательства и предпринимать соответствующие меры....
34070. Система и полномочия органов управления земельными ресурсами 24 KB
  Система и полномочия органов управления земельными ресурсами. Каждый вышестоящий уровень координирует действия нижестоящих а каждый иерархический уровень управления содержит все функции организации субъекта управления. Субъект управления на вышестоящем уровне осуществляет координирование организации субъектов управления на нижестоящих уровнях исходя из принятых для конкретного административнотерриториального образования критериев эффективности рационального использования земель. Система органов государственного управления земельными...
34071. Государственный земельный кадастр: понятие, структура, порядок ведения 38 KB
  Государственный кадастр недвижимости. âО государственном кадастре недвижимостиâ вступил в силу с 01. Государственный кадастровый учёт это действия уполномоченного органа по внесению в Государственный кадастр недвижимости сведений о недвижимом имуществе которые подтверждают существование такой недвижимости как индивидуальноопределённой вещи подтверждают прекращение существования такой недвижимости а также иные сведения предусмотренные ФЗ âОâ государственном кадастре недвижимостиâ. Государственный кадастр недвижимости ...
34072. Землеустройство: назначение, содержание, организация и порядок ведения 39 KB
  Землеустройство это мероприятие по изучению состояния земель планированию и организации рационального использования земель и их охраны по описанию местоположения и или установлению на местности границ объектов землеустройства организации рационального использования земельных участков для сельскохозяйственного производства; организации территорий используемых общинами коренных малочисленных народов Севера Сибири и Дальнего Востока и лицами относящимся к коренным малочисленным народам для обеспечения их традиционного образа жизни....
34073. Возмещение убытков по положениям земельного законодательства 26 KB
  Гражданское законодательство предусматривает при возмещении вреда взыскание убытков которые уже понес потерпевший к моменту предъявления иска в суде. При возмещении вреда причиненного земле речь идет о взыскании в основном будущих расходов на проведение восстановительных работ. определяет размер вреда причиненного окружающей среде в результате нарушения законодательства в области охраны окружающей среды исходя из фактических затрат на восстановление нарушенного состояния окружающей среды с учетом понесенных убытков в том числе упущенной...
34074. Инвентаризация земель в Российской Федерации 23 KB
  Впервые об инвентаризации земель был принят Указ Президента в 1993 г. Процедура порядок инвентаризации. Для инвентаризации земель создаётся специальная комиссия в состав которой включаются представители Росреестра природоохранных органов архитектурноградостроительных и санитарноэпидемиологических органов органов сельского лесного хозяйства представители органов местного самоуправления собственников землевладельцев землепользователей и арендаторов. В результате инвентаризации на каждый земельный участок устанавливается...
34075. Порядок предоставления земельных участков для целей не связанных со строительством 32.5 KB
  С точки зрения процессуальной предоставление земельных участков для целей не связанныхсо строительством не выходит за рамки тех действий которые установлены законодательством для случаев предоставления земель для строительства и которые были изложены выше: подача заявки в компетентный орган формирование земельного участкапринятие решения о его предоставлении государственный кадастровый учет и государственная регистрация прав на земельный участок. 34 ЗК РФ жестко устанавливают обязательные рамки процедуры формирования...
34076. Понятие и содержание управления земельными ресурсами 27.5 KB
  Понятие и содержание управления земельными ресурсами. Управление земельными ресурсами землями это организующая деятельность компетентных органов исполнительной власти по обеспечению рационального использования и охраны земель всеми субъектами земельных отношений. Общее управление земельными ресурсами осуществляется органами общей и специальной компетенции и имеет территориальный характер т. Ведомственное отраслевое управление земельными ресурсами осуществляется государственными комитетами федеральными агентствами федеральными службами...