WikiSort.ru - Программирование

Плавная сортировка (англ. Smoothsort) — алгоритм сортировки выбором, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную O(n log n). Преимущество плавной сортировки в том, что её сложность приближается к O(n), если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.

Общее представление

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

• Массив любой длины может быть также разбит на части размера L(x).
• Не должно быть двух куч одинакового размера, потому что в этом случае последовательность превратится в строго убывающую по размерам.
• Не должно быть двух куч, размеры которых равны двум последовательным числам Леонардо, за исключением массива длины 2.

Эти положения могут быть доказаны.

Каждая куча размера L(x) состоит, слева направо, из подкучи размера L(x − 1), подкучи размера L(x − 2) и корня, за исключением куч размера L(1) и L(0), которые состоят только из корня. Для каждой кучи выполняется следующее свойство: значение корня должно быть не меньше значений корней его куч-потомков (и, как следствие, не меньше значений всех узлов его куч-потомков). Для последовательности куч в свою очередь выполняется следующее свойство: значение корня каждой кучи должно быть не меньше значения корня кучи слева. Следствие этого — крайний правый узел в последовательности будет иметь наибольшее значение, и, что важно, частично отсортированный массив не будет нуждаться в перестановке элементов, для того чтобы стать правильной последовательностью куч. Это является источником приспособляемости алгоритма. Алгоритм прост. Сначала происходит разделение неотсортированного массива на кучу с одним элементом и неотсортированную часть. Куча с одним элементом, очевидно, представляет собой правильную последовательность куч. Последовательность начинает расти путём добавления по одному элементу справа за раз (если нужно, элементы меняются местами, чтобы выполнялось свойство кучи и свойство последовательности), пока не достигнет размера изначального массива. И с этого момента крайний правый элемент в последовательности куч будет самым большим для любой кучи, а, следовательно, будет находиться на верной, конечной позиции. Затем последовательность куч уменьшается до кучи с одним элементом при помощи удаления крайнего правого узла и изменения позиций элементов для восстановления состояния кучи. Как только останется куча с одним элементом, массив будет отсортирован.

Операции

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

Используемая память

Алгоритм плавной сортировки требует памяти для хранения размеров всех куч в последовательности. Так как все эти значения различны, как правило, для этой цели применяется битовая карта. Кроме того, так как в последовательности не больше O(log n) чисел, биты могут быть закодированы О(1) машинными словами при условии использования трансдихотомической модели.

Ссылки

• Плавная сортировка (Smooth_sort)
• E. W. Dijkstra. Smoothsort — an alternative to sorting in situ (EWD-796a) (англ.)

В этой статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из-за отсутствия сносок. Утверждения, не подкреплённые источниками, могут быть поставлены под сомнение и удалены. Вы можете улучшить статью, внеся более точные указания на источники.