Доброго времени суток, читатели, зрители моего канала programmer's notes, любители языка Python. Не забывайте подписываться и писать свои
комментарии к моим статьям и видео.
Пирамидальная сортировка на языке программирования Python
Для понимания того, как работает пирамидальная сортировка придется обратиться к графическому представлению.
Пирамидальная сортировка основывается на древовидной структуре, называемой пирамидой. Рассмотрим рис. 1. В верхней части рисунка представлено дерево, обладающее следующими свойствами.
- Дерево имеет один корень. Все узлы дерева имеют количественный атрибут. В нашем случае это просто целые числа. Будем называть это значением узла.
- Каждый узел, кроме самых верхних, которые называются листьями, может иметь не более 2 потомков. Если количество узлов четное, то один узел будет иметь одного потомка - лист. Узлы, имеющие потомки, будем называть родителями.
- Значение узла должно быть больше значений своих потомков.
- Значение левого потомка узла должно быть больше правого значения данного узла.
- Нами построено дерево, начинающееся с наибольшего значения, но аналогичное дерево может быть построено по принципу убывания.
Мы видим из рис.1, что в общем случае такое дерево не позволяет осуществлять двоичный поиск, но у него два очень важных свойства:
- Корнем его всегда является наибольше значение во всем наборе.
- Дерево очень легко может налагаться на массив. Если i это индекс элемента массива (индекс начинается с 0), то элемент с индексом 2 * i + 1 - это левый его потомок, 2 * i + 2 - правый потомок. Т.е. дерево может быть представлено обычным массивом, для которого выполняются представленные выше 5 положений. Этот массив также представлен на рис. 1.
В общем случае пирамидальное дерево не является отсортированным. Возникает вопрос, как можно его использовать для сортировки. Обратим внимание на два момент:
- В корне всегда находится наибольший в массиве элемент.
- Любой массив в сущности уже есть пирамидальное дерево, у которого, возможно, есть нарушения в правилах, регламентирующих соотношения значений родителя и двух его потомков, а также левого и правого потомка.
Теперь представим себе следующее. Мы имеем алгоритм, который исправляет ошибки в дереве.
- Применим в начале алгоритм ко всему дереву. Дерево становится правильным.
- Поменяем местами первый и последний элемент (элемент с номером n-1, n - длина массива).
- Применим алгоритм к дереву, без последнего элемента массива.
- Продолжим процесс, уменьшая размер обрабатываемого массива каждый раз на 1.
Таким образом у нас получается общий алгоритм сортировки, которую мы и назвали пирамидальной.
Теперь займемся разработкой программы сортировки. Начнем с разработки функции, которая исправляет дерево.
Обратимся к функции fixnode() во фрагменте ниже. Функция получает массив, его длину и номер элемента в массиве. Далее идет проверка условий пирамиды, которые мы описали выше. При необходимости происходит перестановка трех элементов: узла и двух его потомков (если их три). В случае, если потомок один, то все гораздо проще. С помощью функции sort3() сортируются три вершины. После чего расставляются согласно требованиям пирамиды.
В функции fixnode() не хватает одного важного момента. Перестановка элементов может привести к тому, что будет нужна правка для вершин выше, т.е. там, где потомки уже становятся родителями. И т.д. Решить эту проблему можно рекурсивно, вызывая в конце функции дважды
fixnode(ls, n, lc) # левая ветвь
fixnode(ls, n, rc) # правая ветвь
Для того, чтобы полностью построить всю пирамиду нужно вызывать функцию в цикле.
После того, как пирамида получена, можно осуществлять описанный выше алгоритм: 1. первый элемент переставляем с последним. 2. восстанавливаем пирамиду из оставшихся элементов и повторяем, пока элементы не кончаться.
Ниже представлен остальная часть программы пирамидальной сортировки. Далее ссылка на весь текст программы.
В представленный выше программе алгоритм основан на том, что упорядочение необходимо и между прямыми потомками. Но в действительности это совсем необязательно. Важно только чтобы родитель был больше своих потомков. Поэтому функцию fixnode() можно значительно оптимизировать и по объему кода и скорости.
Ниже представлена усовершенствованная функция fixnode().
Ну, пока всё. Пирамидальная сортировка к вашим услугам.
Предыдущая статья о сортировке...
Следующая статья о сортировке...
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.
