Изменения

'''Плавная сортировка''' (англ. 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>, которые задаются следующим образом:

L(n):=

1 & :\mathrm{if}\ n = 0, \\ 1 & :\mathrm{if}\ n = 1, \\ L(n-1)+L(n-2)+1 & :\mathrm{if}\ n > 1. \\

|statement= Любое натуральное число можно представить суммой из представимо в виде суммы <tex dpi = 120> O(\log{N}) </tex> различных чисел Леонардо.}} {{Утверждение|statement= <tex dpi = 120> L(n) = 2 \cdot F(n + 1) - 1 </tex>, где <tex dpi = 120> F(n + 1) </tex> {{---}} <tex dpi 120> (n + 1) </tex>-ое число Фибоначчи.|proof= Это утверждение доказывается по индукции. База: <tex dpi =120> L(0) = 2 \cdot F(1) - 1 = 1 </tex>. Пусть для <tex dpi = 120> n </tex> первых чисел это равенство выполняется. Делаем индуктивный переход: <tex dpi =120> L(n + 1) = L(n) + L(n - 1) + 1 = 2 \cdot F(n + 1) - 1 + 2 \cdot F(n) - 1 + 1 = 2 \cdot F(n + 2) - 1 </tex>. Утверждение доказано.

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

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

Сортируемый Будем поддерживать следующий инвариант:* сортируемый массив делится на группу подмассивов. Каждый ,* каждый подмассив представляет собой структуру данных {{---}} куча. Каждая ,* каждая куча имеет размер равный одному из чисел Леонардо. Размеры ,* размеры куч строго убывают слева направо. При ,* при этом не существует двух куч, имеющих одинаковый размер. В дальнейшем эту группу подмассивов будем называть последовательность куч. Будем поддерживать инвариант последовательности: корни ,* значения ключей в корнях деревьев идут в порядке возрастания слева направо, и инвариант куч: * в самих кучах значение в детях меньше либо равно значению в родителе.В дальнейшем эту группу подмассивов будем называть последовательностью куч.

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

При конструировании последовательности куч будем последовательно выполнять вставку по очереди вставлять в конец новых элементовновые элементы, а при операции получении отсортированного массива будем {{---}} удалять максимальный элемент из последовательности. Следовательно , нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого в начале последовательности располагаются кучи максимального размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности. Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти индекс корня кучи слева от неё. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <tex dpi = 120> (n - 1) </tex>-ая, а правым является <tex dpi = 120> (n - 2) </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}) </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> передается индекс корня кучи, с которой начинаем восстановление.

j = prev(i) <font color = "green">// j - индекс корня соседней кучи</font> '''while''' A[j] > A[i] '''and''' A[j] > A[left(i)] '''and''' A[j] > A[right(i)] swap(A[j], A[i]) i = j j = prev(i) siftDown(i)

==Сложность= Уменьшение последовательности куч путём удаления элемента справа ===Если размер крайней правой кучи равен <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(N \log{N}) </tex>.

==Сложность=Получение отсортированного массива=== Во время построения Так как удаление максимального элемента из последовательности куч <tex dpi = 120> O(N) </tex> раз выполняется вставка элемента. И потом ещё за <tex dpi = 120> O(\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(N) </tex>.

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

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

==Примечание=Связь с быстрой сортировкой===*[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 Википедия -- Числа ЛеонардоХотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для сортировки сравнениями | теореме о нижней оценке]].

* [https://en.wikipedia.org/wiki/Smoothsort Wikipedia {{-- -}} Smoothsort]

* [http://habrahabr.ru/post/133996/ Хабрахабр {{-- -}} И снова про сортировки]

[[Категория: Сортировка]][[Категория: Сортировкина сравнениях]]