Изменения

'''Плавная сортировка''' (англ. 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> L(k) </tex>. Для каждого подмассива выполним операцию '''heapify'''(она выполняется так же, как в [[Двоичная куча|двоичной куче]]), после которой необходимо будет отсортировать корни куч, чтобы выполнялся инвариант а при получении отсортированного массива {{---}} удалять максимальный элемент из последовательности. Следовательно, нам необходимы четыре две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого в начале последовательности располагаются кучи максимального размера), и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности, операция сортировки корней куч и восстановление инварианта последовательности.

Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти корень соседней индекс корня кучи слеваот неё. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <tex dpi = 120> (n - 1) </tex>-ая, а правым является <tex dpi = 120> (n - 2) </tex>-ая куча Леонардо. Для хранения списка длин куч придется выделить <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти.

[[Файл:add-example.png|470px|thumb|right|Пример вставки элемента.(без просеивания вниз)]][[Файл:Leonardo-heap-2.png|470px|thumb|right|Вставка в последовательность куч, показанную выше, числа 13. Далее будет сразу происходить просеивание внутри "зеленого" дерева Леонардо, так как корень соседнего дерева меньше, чем дети корня "зелёного" дерева.]]

Нам не важно выполняется ли в данный момент инвариант После этого необходимо восстановить свойства кучи, потому что позже мы будем выполнять для неё операцию heapify. Так как при выполнении вставки мы смотри только на размеры двух последних куч, то вставка выполняется за <tex dpi = 120> O(1) </tex>. ===Сортировка корней куч=== Для сортировки корней будем использовать [[Сортировка выбором|сортировку выбором]]. Пусть в и последовательности <tex dpi = 120> l = O(\log{N}) </tex> куч. Сортировать будем с конца, то есть в начале текущей назначается последняя куча. Тогда после первой итерации в самой правой куче мы получим максимальный корень. А кучу, из которой этот корень пришел в текущую, после обмена корнем необходимо просеять. А затем уменьшаем <tex dpi = 120> l </tex> на <tex dpi =120> 1 </tex>. Повторяем эти действия, пока <tex dpi = 120> l </tex> не станет равна <tex dpi =120> 1 </tex>. Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то сортировка вставками работает за <tex dpi =120> O(\log^2{N}) </tex>. Просеивание выполняется за <tex dpi =120> O(\log{N}) </tex>, то в итоге алгоритм работает за <tex dpi =120> O(\log^2{N}) + O(\log{N}) \cdot O(\log{N}) = O(\log^2{N})</tex> ===Восстановление свойств последовательности=== Восстановление свойстчто, как правило, достигается при помощи разновидности [[Сортировка вставками|сортировки вставками]] (см. ниже псевдокод):

Операция просеивания значительно упрощена благодаря использованию чисел Просеивание в куче Леонардосильно упрощено, так как каждая куча либо будет одноэлементной, иметь либо будет иметь двух потомков, либо ноль. Нет нужды беспокоиться об отсутствии одной из куч-потомков. Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то модификация сортировки вставками будет работать за <tex dpi = 120> O(\log{N}) </tex>. Просеивание тоже выполняется за <tex dpi = 120> O(\log{N}) </tex>, тогда в итоге операция вставки выполняется за:<tex dpi = 120> O(\log{N}) + O(\log{N}) = O(\log{N}) </tex>.

=== Уменьшение последовательности куч путём удаления элемента справа ===Если размер крайней правой кучи равен <tex dpi = 120> 1 </tex> (то есть <tex dpi = 120> L(1) </tex> или <tex dpi = 120> L(0) </tex>), эта куча просто удаляется.В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой. Так как в последовательности <tex dpi = 120> O(\log{N}) </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> элементовтаких массивах время работы плавной сортировки приближается к линейному. На таком массиве плавная сортировка в среднем будет работать дольше, чем быстрая сортировка в силу того, что константа спрятанная в О-натации Хотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для неё большесортировки сравнениями | теореме о нижней оценке]].

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