Плавная сортировка
алгоритм сортировки выбором, разновидность пирамидальной сортировки Из Википедии, свободной энциклопедии
алгоритм сортировки выбором, разновидность пирамидальной сортировки Из Википедии, свободной энциклопедии
Плавная сортировка (англ. Smoothsort) — алгоритм сортировки выбором, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную O(n log n). Преимущество плавной сортировки в том, что её сложность приближается к O(n), если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.
Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо. Куча состоит из последовательности куч, размеры которых равны одному из чисел Леонардо, а корни хранятся в порядке возрастания. Преимущества таких специальных куч перед двоичными состоят в том, что если последовательность отсортирована, её создание и разрушение займёт O(n) времени, что будет быстрее. Разбить входные данные на кучи просто: крайние слева узлы массива составят самую большую кучу, а оставшиеся будут разделены подобным образом.
Эти положения могут быть доказаны.
Каждая куча размера L(x) состоит, слева направо, из подкучи размера L(x − 1), подкучи размера L(x − 2) и корня, за исключением куч размера L(1) и L(0), которые состоят только из корня. Для каждой кучи выполняется следующее свойство: значение корня должно быть не меньше значений корней его куч-потомков (и, как следствие, не меньше значений всех узлов его куч-потомков). Для последовательности куч в свою очередь выполняется следующее свойство: значение корня каждой кучи должно быть не меньше значения корня кучи слева. Следствие этого — крайний правый узел в последовательности будет иметь наибольшее значение, и, что важно, частично отсортированный массив не будет нуждаться в перестановке элементов, для того чтобы стать правильной последовательностью куч. Это является источником приспособляемости алгоритма. Алгоритм прост. Сначала происходит разделение неотсортированного массива на кучу с одним элементом и неотсортированную часть. Куча с одним элементом, очевидно, представляет собой правильную последовательность куч. Последовательность начинает расти путём добавления по одному элементу справа за раз (если нужно, элементы меняются местами, чтобы выполнялось свойство кучи и свойство последовательности), пока не достигнет размера изначального массива. И с этого момента крайний правый элемент в последовательности куч будет самым большим для любой кучи, а, следовательно, будет находиться на верной, конечной позиции. Затем последовательность куч уменьшается до кучи с одним элементом при помощи удаления крайнего правого узла и изменения позиций элементов для восстановления состояния кучи. Как только останется куча с одним элементом, массив будет отсортирован.
Необходимы две операции: увеличение последовательности куч путём добавления элемента справа и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности куч.
После этого должно быть восстановлено выполнение свойств кучи и последовательности куч, что, как правило, достигается при помощи разновидности сортировки вставками:
Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
Если размер крайней правой кучи равен 1 — то есть это куча L(1) или L(0), — то эта куча просто удаляется. В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства кучи, сначала для левой кучи, затем — для правой.
Алгоритм плавной сортировки требует памяти для хранения размеров всех куч в последовательности. Так как все эти значения различны, как правило, для этой цели применяется битовая карта. Кроме того, так как в последовательности не больше O(log n) чисел, биты могут быть закодированы О(1) машинными словами при условии использования трансдихотомической модели.
 | В статье есть список источников, но не хватает сносок. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
