Изменения

'''Плавная сортировка''' (англ. Smooth sort) {{-- -}} алгоритм сортировки, разновидность модификация [[Сортировка кучей|сортировки кучей]], разработанная разработанный Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную работает за время <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>, которые задаются следующим образом:

<tex dpi = 120> L(0n) = \begin{cases} 1 & \mathrm{if}\ n = 0, L(\\ 1) & \mathrm{if}\ n = 1, \\ L(i) = L(i n- 1) + L(i n- 2) + 1 & \mathrm{if}\ n > 1. \\ \end{cases}</tex>

<tex dpi = 120> 1, 1, 3, 5, 9, 15, 25, 41, ... </tex> {{Утверждение|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> OL(log N0) = 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>. Утверждение доказано.

* Числочисло, записанное в корне , не меньше чисел в поддеревьях,* Левым левым поддеревом является <tex dpi = 120> (k-1) </tex>-я куча Леонардо,* Правым правым — <tex dpi = 120> (k-2) </tex>-я куча Леонардо.

Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность ==Операции над последовательностью куч. При этом корни деревьев идут в порядке возрастания слева направо.==При этом не существует двух конструировании последовательности кучбудем по очереди вставлять в конец новые элементы, имеющих одинаковый размера при получении отсортированного массива {{---}} удалять максимальный элемент из последовательности. Так же никакие Следовательно, нам необходимы две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи. Если мы операции: увеличение последовательности куч путём добавления элемента справа (будем использовать подряд две считать, что в начале последовательности располагаются кучи размерностью <tex dpi = 120> L(xмаксимального размера) </tex> и <tex dpi = 120> Lуменьшение путём удаления крайнего правого элемента (x+1корня последней кучи) </tex>, то их можно будет заменить одной – размерностью <tex dpi = 120> L(x+2) </tex>с сохранением состояния кучи и последовательности.

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

* Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером <tex dpi = 120> 1</tex>. Этот размер полагается равным <tex dpi = 120> L(1) </tex>, кроме случая, когда крайняя правая куча уже имеет размер <tex dpi = 120> L(1) </tex>, тогда размер новой одноэлементной кучи полагают равным <tex dpi = 120> L(0) </tex>.После этого должно быть восстановлено выполнение свойств необходимо восстановить свойства кучи и последовательности куч, что, как правило, достигается при помощи разновидности [[Сортировка вставками|сортировки вставками]](см. ниже псевдокод):

# Пока слева от неё есть куча , и значение её корня больше значения текущего корня и обоих корней куч-потомков:#* Меняются местами новый корень и корень кучи слева (что не нарушит свойство это гарантирует выполнение инварианта для текущей кучи). Эта И куча , с которой произошел обмен, становится текущей.# Выполняется Потом выполняется «просеивание»кучи, на которой остановилась сортировка корней, чтобы выполнялось свойство гарантировать выполнение инварианта кучи:#* Пока размер текущей кучи больше <tex dpi = 120> 1 </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 dpi = 120> O(log Nвозвращает индекс корня ближайшей слева кучи) , <tex>\mathrm{left}</tex> куч(возвращает индекс левого сына), то восстановление свойства последовательности выполняется за <tex dpi = 120> O\mathrm{right}</tex> (log Nвозвращает индекс правого сына) уже реализованы. В функцию <tex>\mathrm{ensureSequence}</tex>передается индекс корня кучи, с которой начинаем восстановление.<code> '''function''' ensureSequence(i: '''int'''): 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)</code>

===Построение последовательности===Последовательность куч получается при вставке элементов массива по очереди в эту самую последовательность. Получаем время работы <tex dpi = 120> O(N \log{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>. ===Связь с быстрой сортировкой===На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в худшем случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку. Так реализована сортировка в стандартной библиотеке языка С++. Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы на некоторых тестах, так как после нескольких итераций быстрой сортировки массив окажется почти отсортированным, а на таких массивах время работы плавной сортировки приближается к линейному. Хотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для сортировки сравнениями | теореме о нижней оценке]]. ==См. также==* [[Сортировка кучей|Сортировка кучей]]* [[Быстрая сортировка|Быстрая сортировка]] ==Примечания== <references />

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

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

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