3622
правки
Изменения
м
→Примечание
'''Плавная сортировка''' (англ. Smooth sort) {{---}} алгоритм сортировки, модификация [[Сортировка кучей|сортировки кучей]], разработанный Э. Дейкстрой. Как и пирамидальная сортировка, в худшем случае работает за время <tex> \Theta(N\log{N}) </tex>. Преимущество плавной сортировки в том, что её сложность время работы приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей сложность всегда одна, независимо время работы не зависит от состояния входных данных.
==Основная идея==
{{Утверждение
|statement= Любое натуральное число можно представимо в виде суммы из <tex dpi = 120> O(\log{N}) </tex> различных чисел Леонардо.
}}
При конструировании последовательности куч будем по очереди вставлять в конец новые элементы, а при получении отсортированного массива {{---}} удалять максимальный элемент из последовательности. Следовательно, нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что в начале последовательности располагаются кучи максимального размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности.
Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти индекс корня соседней кучи слева от неё. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <tex dpi = 120> (n - 1) </tex>-ая, а правым является <tex dpi = 120> (n - 2) </tex>-ая куча Леонардо. Для хранения списка длин куч придется выделить <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти.
===Вставка элемента===
===Восстановление свойств последовательности===
Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции '''''<tex>\mathrm{prev''''' }</tex> (возвращает индекс корня ближайшей слева кучи), '''''<tex>\mathrm{left''''' }</tex> (возвращает индекс левого сына), '''''<tex>\mathrm{right''''' }</tex> (возвращает индекс правого сына) уже реализованы. В функцию '''''<tex>\mathrm{ensureSequence''''' }</tex> передается индекс корня кучи, с которой начинаем восстановление.
<code>
'''function''' ensureSequence(i: '''int'''):
===Получение отсортированного массива===
Так как удаление максимального элемента из последовательности выполняется за <texdpi = 120> O(\log n{N})</tex>, то время работы сортировки составляет <tex dpi = 120> O(N\log{N}) </tex>.
===Лучший случай===
===Связь с быстрой сортировкой===
На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в худшем случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку. Так реализована стандартная сортировка в стандартной библиотеке языка С++. Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы на некоторых тестах, так как после нескольких итераций быстрой сортировки массив окажется почти отсортированным, а на таких массивах время работы плавной сортировки приближается к линейному. Хотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для сортировки сравнениями | теореме о нижней оценке]].
==См. также==
* [[Быстрая сортировка|Быстрая сортировка]]
==ПримечаниеПримечания==
<references />
