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

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

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

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

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

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


 

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

27057. Учет амортизации ос и нма 16.44 KB
  Учет амортизации ос и нма Счет 10400 Амортизация Счет предназначен для сбора информации о начисленной сумме амортизации объектов нефинансовых активов принятых учреждением к учету. В течение финансового года амортизация начисляется ежемесячно в размере 1 12 годовой суммы. По объектам основных средств амортизация начисляется: на объект недвижимого имущества при принятии его к учету по факту государственной регистрации: стоимостью до 40000 рублей включительно амортизация начисляется в размере 100 балансовой стоимости объекта при принятии к...
27058. Анализ обеспеченности учреждения трудовыми ресурсами 13.33 KB
  Анализ обеспеченности учреждения трудовыми ресурсами К трудовым ресурсам относится та часть населения которая обладает необходимыми физическими данными знаниями и навыками труда в соответствующей отрасли. В частности от обеспеченности учреждения трудовыми ресурсами и эффективности их использования зависят объем и своевременность выполнения всех работ эффективность использования оборудования. Общую картину состояния и тенденции развития трудовых ресурсов учреждения дает анализ изменения среднесписочной численности работников...
27059. Нормативное регулирование бухгалтерского учета в РФ 14.67 KB
  Нормативное регулирование бухгалтерского учета в РФ Нормативное регулирование бухгалтерского учета включает: 1 нормативное правовое регулирование осуществляется нормами права содержащимися в соответствующих нормативных правовых актах; 2 методическое нормативнотехническое регулирование осуществляется методическими техническими нормами содержащимися в соответствующих актах методического нормативнотехнического характера. Первый уровень законы Российской Федерации и указы президента РФ устанавливающие единые правовые и...
27060. Ревизия расчетов с поставщиками и подрядчиками 12.31 KB
  Ревизия расчетов с поставщиками и подрядчиками Цель установление правомерности и эффективности использования средств бюджетов при осуществлении рассветных операции с поставщиками и подрядчиками.02 N2П О безналичных расчетах в РФ Источники ревизии: 1Первичка 2регистры аналитического и синтетического учета 3отчетность учреждении 4Государственные контракты в рамках N94ФЗ О государственных закупках 5СчетФактуранакладная 6акт приема передачи выполненных работоказанных услуг 7доверенность 8денежные документы 9журнал операции с...
27061. Состав бухгалтерской отчетности НКО 14.62 KB
  Состав бухгалтерской отчетности НКО Некоммерческие организации составляют и представляют отчетность установленную законодательными и нормативными актами для юридических лиц.14 Закона о бухгалтерском учете бухгалтерская отчетность организаций за исключением отчетности бюджетных организаций а также общественных организаций объединений и их структурных подразделений не осуществляющих предпринимательской деятельности и не имеющих кроме выбывшего имущества оборотов по реализации товаров работ услуг включает: Бухгалтерский баланс; ...
27062. Учет кассовых операций 14.76 KB
  Учет кассовых операций Порядок хранения расходования и учета денежных средств в кассе установлен Инструкцией Центрального банка РФ и Инструкцией по бюджетному учету № 174н. Для учета движения наличных денежных средств в валюте Российской Федерации и в иностранной валюте в кассе учреждения используют счет 020134000 Касса . Прием в кассу наличных денежных средств от физических лиц производится по бланкам строгой отчетности утвержденным в порядке предусмотренном законодательством Российской Федерации и Приходным кассовым ордерам ф. В случае...
27063. Учет расчетов с подотчетными лицами 14.33 KB
  Учет расчетов с подотчетными лицами Подотчетными суммами называются денежные авансы выдаваемые работникам учреждения из кассы на мелкие хозяйственные расходы и на расходы по командировкам. Аналитический учет расчетов с подотчетными лицами ведется в разрезе подотчетных лиц видов выплат и видов расчетов расчеты по выданным денежным средствам расчеты по полученным денежным документам в Карточке учета средств и расчетов либо в Журнале по расчетам с подотчетными лицами. Для учета расчетов с подотчетными лицами по суммам денежных средства и...
27064. Учет расчетов по недостачам 15.83 KB
  Учет расчетов по суммам выявленных недостач и хищений денежных средств и ценностей сумм потерь от порчи материальных ценностей и других сумм подлежащих удержанию и списанию в установленном порядке осуществляют на счете 020900000 Расчеты по недостачам . Учет расчетов по недостачам хищениям ведется в соответствии с КОСГУ на следующих счетах: 020971000 Расчеты по ущербу основным средствам ; 020972000 Расчеты по ущербу нематериальным активам ; 020973000 Расчеты по ущербу непроизведенным активам ; 020974000 Расчеты по ущербу материальных...
27065. Учет удержаний из заработной платы 16.39 KB
  Учет удержаний из заработной платы Счет 30403 Расчеты по удержаниям из выплат по оплате труда Счет предназначен для учета расчетов по удержаниям из заработной платы и денежного довольствия стипендий; безналичным перечислениям на счета во вклады сотрудников учреждения; взносам по договорам добровольного страхования; взносам на пенсионное страхование; суммам членских профсоюзных взносов; исполнительным листам и другим документам. Удержания производятся на основании соответствующих документов: письменных заявлений работников договоров...