212
правок
Изменения
Нет описания правки
'''Плавная сортировка''' (англ. Smooth sort) -- алгоритм сортировки, разновидность [[Сортировка кучей|сортировки кучей]], разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную <tex dpi = 120> O(N log N) </tex>. Преимущество плавной сортировки в том, что её сложность приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у пирамидальной сортировки кучей сложность всегда одна, независимо от состояния входных данных.
==Основная идея==
Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:
Вот первые несколько членов этой последовательности:
<tex dpi = 120> 1, 1, 3, 5, 9, 15, 25, 41, ... </tex>
{{Утверждение
}}
[[Файл:leonardo-heap.png|600px|thumb|right|Пример последовательности куч с указанными размерами куч]]
Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом корни деревьев идут в порядке возрастания слева направо.
При этом не существует двух куч, имеющих одинаковый размер. Так же никакие две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи.
Если мы будем использовать подряд две кучи размерностью <tex dpi = 120> L(x) </tex> и <tex dpi = 120> L(x+1) </tex>, то их можно будет заменить одной – размерностью <tex dpi = 120> L(x+2) </tex>.
* Пока последовательность куч не пустая достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
==Операциинад последовательностью куч==
Необходимы две операции: увеличение последовательности куч путём добавления элемента справа и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности куч.
===Вставка элемента===
