212
правок
Изменения
Нет описания правки
'''Плавная сортировка''' (англ. Smooth sort) {{-- -}} алгоритм сортировки, разновидность модификация [[Сортировка кучей|сортировки кучей]], разработанная разработанный Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную <tex dpi = 120> O(N \log {N}) </tex>. Преимущество плавной сортировки в том, что её сложность приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей сложность всегда одна, независимо от состояния входных данных.
==Основная идея==
<tex dpi = 120> L(0n) := \begin{cases} 1 & :n = 0, L(\\ 1) & :n = 1, \\ L(i) = L(i n- 1) + L(i n- 2) + 1 & :n > 1. \\ \end{cases}</tex>
Вот первые несколько членов этой последовательности:
{{Утверждение
|statement= Любое натуральное число можно представить суммой из <tex dpi = 120> O(\log {N}) </tex> различных чисел Леонардо.
}}
|definition =
'''''K-ая куча Леонардо''''' — это двоичное дерево с количеством вершин <tex dpi = 120> L(k) </tex>, удовлетворяющее следующим условиям:
* Числочисло, записанное в корне не меньше чисел в поддеревьях,* Левым левым поддеревом является <tex dpi = 120> (k-1) </tex>-я куча Леонардо,* Правым правым — <tex dpi = 120> (k-2) </tex>-я куча Леонардо.
}}
Можно заметить, что куча Леонардо очень похожа на Биномиальную кучу. Куча Леонардо используется из-за свойства, что у каждой вершины либо два, либо ноль детей. [[Файл:leonardo-heap.png|600px|thumb|right|Пример последовательности куч с указанными размерами (список хранит номера чисел Леонардо, соответствующих размерам куч)]]Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. Размеры куч строго убывают слева направо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилуне существует двух куч, имеющих одинаковый размер. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом Будем поддерживать инвариант последовательности: корни деревьев идут в порядке возрастания слева направо, и инвариант куч: значение в детях меньше либо равно значению в родителе.
'''Алгоритм состоит из двух стадийШаг 1:'''Превращение массива в последовательность куч* Конструирование последовательности куч* '''Шаг 2:''' Пока последовательность куч не пустая достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
==Операции над последовательностью куч==
===Вставка элемента===
[[Файл:add-example.png|470px|thumb|right|Пример вставки элемента (без просеивания вниз)]]
При добавлении в последовательность нового элемента возможны две ситуации:
* Если две последние кучи имеют размеры <tex dpi = 120> L(x + 1) </tex> и <tex dpi = 120> L(x) </tex> (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного <tex dpi = 120> L(x+2) </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}) + O(\log {N}) = O(\log {N}) </tex>. ====Восстановление свойств последовательности==== Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции '''''prev''''' (возвращает индекс корня ближайшей слева кучи), '''''left''''' (возвращает индекс левого сына), '''''right''''' (возвращает индекс правого сына) уже реализованы. В функцию '''''ensureSequence''''' передается индекс корня кучи, с которой начинаем восстановление.<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> 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 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(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> дополнительной памяти для хранения длин куч в последовательности куч. ==Примечание==*[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 Википедия -- Числа Леонардо] ==См. также==* [[Сортировка кучей|Сортировка кучей]]* [[Быстрая сортировка|Быстрая сортировка]]
==Источники информации==
