Изменения

'''Плавная сортировка''' (англ. Smooth sort) {{---}} алгоритм сортировки, модификация [[Сортировка кучей|сортировки кучей]], разработанный Э. Дейкстрой. Как и пирамидальная сортировка, имеет сложность в худшем случае равную работает за время <tex dpi = 120> O\Theta(N\log{N}) </tex>. Преимущество плавной сортировки в том, что её сложность время работы приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей сложность всегда одна, независимо время работы не зависит от состояния входных данных.

Будем развивать Разовьём идею пирамидальной сортировки. Для этого будем использовать используем не [[Двоичная куча|двоичную кучу]], а специальную, полученную с помощью чисел Леонардо<ref>[https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9B%D0%B5%D0%BE%D0%BD%D0%B0%D1%80%D0%B4%D0%BE Википедия {{---}} Числа Леонардо]</ref>, которые задаются следующим образом:

|statement= Любое натуральное число можно представить суммой из представимо в виде суммы <tex dpi = 120> O(\log{N}) </tex> различных чисел Леонардо.

* число, записанное в корне , не меньше чисел в поддеревьях,

Можно заметить, что куча Леонардо очень похожа на [[Биномиальная куча|биномиальную]]. Куча Леонардо используется из-за своих свойств.

* каждый подмассив представляет собой структуру данных {{---}} куча,

В дальнейшем эту группу подмассивов будем называть последовательность последовательностью куч.

'''Шаг 2:''' Пока последовательность куч не пустая , достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.

При конструировании последовательности куч будем последовательно выполнять вставку по очереди вставлять в конец новых элементовновые элементы, а при операции получении отсортированного массива будем {{---}} удалять максимальный элемент из последовательности. Следовательно, нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого в начале последовательности располагаются кучи максимального размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности.

Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти корень соседней индекс корня кучи слеваот неё. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <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> передается индекс корня кучи, с которой начинаем восстановление.

Получение последовательности Последовательность куч, для которых не выполняется инвариант, очевидно производится за <tex dpi = 120> O(N) </tex>. По указанному выше утверждению <tex dpi = 120> N </tex> можно представить получается при вставке элементов массива по очереди в виде суммы длин кучэту самую последовательность. Пусть <tex dpi = 120> N = L(k_1) + L(k_2) + ... + L(k_n) </tex>, тогда выполнение операции '''heapify''' для всех куч выполнится за <tex dpi = 120> O(L(k_1)) + O(L(k_2)) + ... + O(L(k_n)) = O(N) </tex>. В итоге построение последовательности выполняется за Получаем время работы <tex dpi = 120> O(N) + O(N) + O(\log^2{N}) = O(N) </tex>.

Так как <tex dpi = 120> O(N) </tex> выполняется удаление максимального элемента из последовательности, то вся эта операция выполняется за <tex dpi = 120> O(N\log{N}) </tex>. Следовательно, сортировка в худшем случае выполняется за то время работы сортировки составляет <tex dpi = 120> O(N\log{N}) </tex>.

===Лучший случай===Однако если подать на вход плавной сортировке уже отсортированный массив, асимптотика будет составлять <tex dpi = 120> O(N) </tex>. Дело в том, что операция :*Операция добавления элемента последовательности на таком примере будет выполняться за <tex dpi = 120> O(1) </tex>, из-за того, что в конец будет добавляться максимальный элемент и просеивание будет сразу останавливаться.*Операция получения и удаления максимального элемента будет также выполняться за <tex dpi = 120> O(1) </tex>, потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи. В итоге на таком примере получается асимптотика <tex dpi = 120> O(N) </tex>.

* требует <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти для хранения длин куч в последовательности. Однако с помощью некоторых модификации модификаций расходы на дополнительную память можно получить сократить до <tex dpi 120> O(1) </tex> дополнительной памяти.

На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в самом плохом худшем случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку кучей. Так реализована стандартная сортировка в стандартной библиотеке языка С++. Однако чтобы Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы в на некоторых случаяхтестах, можно вместо так как после нескольких итераций быстрой сортировки кучей использовать плавную сортировку. Может показаться, что если ограничить глубину рекурсии некоторым числом <tex dpi = 120> D </tex>, независящим от <tex dpi = 120> N </tex>, то быстрая сортировка может начать работать за линейное время. Это ложное утверждение, потому как легко составить пример, на котором сортировка станет работать дольше. Например, пусть сортировке на вход подан массив из <tex dpi =120> 10^9 \cdot D </tex> элементов. На таком массиве возможна ситуацияокажется почти отсортированным, когда разделяющий элемент может каждый раз оказываться минимальным или максимальным. Тогда а на вход плавная сортировка получит массив из <tex dpi = 120> 10^9 </tex> элементовтаких массивах время работы плавной сортировки приближается к линейному. На таком массиве плавная сортировка в среднем будет работать дольше, чем быстрая сортировка в силу того, что константа спрятанная в О-натации Хотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для неё большесортировки сравнениями | теореме о нижней оценке]].

==ПримечаниеПримечания==