Smoothsort

Плавная сортировка (англ. Smooth sort) -- алгоритм сортировки, разновидность сортировки кучей, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную [math] O(N log N) [/math]. Преимущество плавной сортировки в том, что её сложность приближается к [math] O(N) [/math], если входные данные частично отсортированы, в то время как у сортировки кучей сложность всегда одна, независимо от состояния входных данных.

Основная идея

Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:

[math] L(0) = 1, L(1) = 1, L(i) = L(i - 1) + L(i - 2) + 1 [/math]

Вот первые несколько членов этой последовательности: [math] 1, 1, 3, 5, 9, 15, 25, 41, ... [/math]

Утверждение:

Любое натуральное число представить суммой из [math] O(log N) [/math] различных чисел Леонардо.

Определение:

K-ая куча Леонардо — это двоичное дерево с количеством вершин [math] L(k) [/math], удовлетворяющее следующим условиям: Число, записанное в корне не меньше чисел в поддеревьях Левым поддеревом является [math] (k-1) [/math]-я куча Леонардо Правым — [math] (k-2) [/math]-я куча Леонардо

Пример последовательности куч с указанными размерами куч

Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом корни деревьев идут в порядке возрастания слева направо.

При этом не существует двух куч, имеющих одинаковый размер. Так же никакие две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи. Если мы будем использовать подряд две кучи размерностью [math] L(x) [/math] и [math] L(x+1) [/math], то их можно будет заменить одной – размерностью [math] L(x+2) [/math].

Алгоритм представляет из себя несколько стадий:

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

Операции над последовательностью куч

Необходимы две операции: увеличение последовательности куч путём добавления элемента справа и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности куч.

Вставка элемента

• Если две последние кучи имеют размеры [math] L(x + 1) [/math] и [math] L(x) [/math] (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного [math] L(x+2) [/math]. Для неё свойство кучи необязательно.
• Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером 1. Этот размер полагается равным [math] L(1) [/math], кроме случая, когда крайняя правая куча уже имеет размер [math] L(1) [/math], тогда размер новой одноэлементной кучи полагают равным [math] L(0) [/math].

После этого должно быть восстановлено выполнение свойств кучи и последовательности куч, что, как правило, достигается при помощи разновидности сортировки вставками:

1. Крайняя правая куча (сформированная последней) считается «текущей» кучей.
2. Пока слева от неё есть куча и значение её корня больше значения текущего корня и обоих корней куч-потомков:
   • Меняются местами новый корень и корень кучи слева (что не нарушит свойство для текущей кучи). Эта куча становится текущей.
3. Выполняется «просеивание», чтобы выполнялось свойство кучи:
   • Пока размер текущей кучи больше 1 и значение корня любой из куч-потомков больше значения корня текущей кучи:
     • Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.

Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.

Так как в последовательности [math] O(log N) [/math] куч и просеивание можно выполнить за [math] O(log N) [/math], то время вставки равно: [math] O(log N) + O(log N) = O(log N) [/math].

Уменьшение последовательности куч путём удаления элемента справа

Если размер крайней правой кучи равен 1 (то есть [math] L(1) [/math] или [math] L(0) [/math]), эта куча просто удаляется. В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. что корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.

Так как в последовательности [math] O(log N) [/math] куч, то восстановление свойства последовательности выполняется за [math] O(log N) [/math].

Сложность

Во время построения последовательности куч [math] O(N) [/math] раз выполняется вставка элемента. И потом ещё [math] O(N) [/math] раз выполняется удаление элемента при процедуре получения отсортированного массива. Таким образом сложность плавной сортировки составляет [math] O(N log N) [/math].

Однако если подать на вход плавной сортировке уже отсортированный массив асимптотика будет составлять [math] O(N) [/math]. Дело в том, что во время процедуры получения последовательности куч мы всегда будем вставлять элемент, который больше остальных уже находящихся в последовательности. Поэтому восстановление свойства последовательности будет выполняться за [math] O(1) [/math] (так как алгоритм только посмотрит на корень соседней кучи, а просеивание закончится сразу потому что новый элемент будет больше своих детей). Операция получения и удаления максимального элемента будет тоже выполняться за [math] O(1) [/math], потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи. В итоге, так как алгоритм [math] O(N) [/math] раз вставляет, а потом и удаляет элементы, получается асимптотика [math] O(N) [/math].

Достоинства

• худшее время работы -- [math] O(N log N) [/math]
• время работы в случае, когда подается отсортированный массив -- [math] O(N) [/math]

Недостатки

• не является устойчивой
• требует [math] O(N) [/math] дополнительной памяти для хранения последовательности куч

Источники информации

• Wikipedia -- Smoothsort
• Smoothsort Demystified
• Хабрахабр -- И снова про сортировки