Изменения

Перейти к: навигация, поиск

Smoothsort

261 байт добавлено, 23:53, 15 июня 2015
м
Примечание
'''Плавная сортировка''' (англ. 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>, которые задаются следующим образом:
<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:''' Пока последовательность куч не пустая , достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
==Операции над последовательностью куч==
При конструировании последовательности куч будем последовательно выполнять вставку по очереди вставлять в конец новых элементовновые элементы, а при операции получении отсортированного массива будем {{---}} удалять максимальный элемент из последовательности. Следовательно, нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого в начале последовательности располагаются кучи максимального размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности.
Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину , можно найти индекс корня соседней кучи слеваот неё. Чтобы искать индексы детей вершины , надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <tex dpi = 120> (n - 1) </tex>-ая, а правым является <tex dpi = 120> (n - 2) </tex>-ая куча Леонардо. Для хранения списка длин куч придется выделить <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти.
===Вставка элемента===
* Если две последние кучи имеют размеры <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}) </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> передается индекс корня кучи, с которой начинаем восстановление.
<code>
'''function''' ensureSequence(i: '''int'''):
</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(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(\log{N}) </tex> дополнительной памяти для хранения длин куч в последовательности. Однако с помощью некоторых модификации модификаций расходы на дополнительную память можно получить сократить до <tex dpi 120> O(1) </tex> дополнительной памяти.
===Связь с быстрой сортировкой===
На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в самом плохом худшем случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку кучей. Так реализована стандартная сортировка в стандартной библиотеке языка С++. Однако чтобы Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы в на некоторых случаяхтестах, можно вместо так как после нескольких итераций быстрой сортировки массив окажется почти отсортированным, а на таких массивах время работы плавной сортировки приближается к линейному. Хотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для сортировки кучей использовать плавную сортировкусравнениями | теореме о нижней оценке]]==Примечание== <references />
==См. также==
* [[Сортировка кучей|Сортировка кучей]]
* [[Быстрая сортировка|Быстрая сортировка]]
 
==Примечания==
 
<references />
==Источники информации==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]
[[Категория: Сортировки на сравнениях]]

Навигация