Smoothsort

Smoothsort (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 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, 3, 5, 9, 15, 25, 41, ... [/math]

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

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

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

При этом не существует двух куч, имеющих одинаковый размер. Это утверждение можно доказать так: Числа Леонардо растут медленнее функции [math] 2^N [/math], поэтому для любого массива можно найти такое число Леонардо, которое будет больше середины. Исключением является массив длины 2.

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

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

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