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-ая куча Леонардо — это двоичное дерево с количеством вершин L(k), удовлетворяющее следующим условиям: Число, записанное в корне не меньше чисел в поддеревьях Левым поддеревом является (k-1)-я куча Леонардо Правым — (k-2)-я

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

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

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