Плавный метод сортировки

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

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

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

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

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

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

Увеличение последовательности куч путем добавления элемента справа достигается при следующих условиях:

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

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

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

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

Уменьшение последовательности куч путем удаления элемента справа достигается при следующих условиях:

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

Постановка задачи

Название приложения: Программа сортировки методами выбора Назначение разработки: Исходя из введенных пользователем данных отсортировать тремя методами сортировки: выборкой, пирамидально, плавной.

Входные данные вводятся пользователем в специальные поля. После обработки и выполнения сортировки программа выводит результат в соответствующее поле вывода.

Для корректной работы программы требуется заполнить все необходимые поля. Для реализации данной программы мы используем язык программирования C#, на платформе Visual Studio.

Системные требования к ПК:

• 1) Операционная система Windows 7 или выше.
• 2) Свободное место на жестко диске: 10Мб и более.
• 3) Наличие Net. Framework 4.0 или выше.
• 4) Оперативная память 512Мб и выше.
• 5) Клавиатура и мышь.

пирамидальный сортировка просеивание алгоритм.