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 />
