Пирамидальная сортировка

Пирамидальная сортировка

После того, как мы реализовали очередь по приоритету в виде сортирующего дерева, можно утверждать, что такое дерево можно использовать как алгоритм сортировки: одновременно добавлять в сортирующее дерево ряд элементов, а затем выбирать их по одному в требуемом порядке. (Обратите внимание, что в случае применения описанного метода элементы выбираются в обратном порядке. Т.е. вначале выбирается наибольший элемент. Однако если использовать обратный метод сравнения, элементы можно извлекать в порядке их возрастания.)

Не удивительно, что алгоритм сортировки с помощью сортирующего дерева называется пирамидальной сортировкой (heapsort). Если припоминаете, в главе 5 рассмотрение этого метода сортировки было отложено до приобретения необходимых теоретических сведений.

Только что названный алгоритм состоит в следующем: предположим, что у нас имеется очередь по приоритету, реализованная в виде сортирующего дерева с выбором минимального элемента. Мы добавляем в него все элементы, а затем удаляем их по одному. Если бы вначале в структуре TList хранились неотсортированные элементы, применение этого алгоритма означало бы, что все элементы копировались бы из одной структуры TList в другую, а затем обратно. Намного более предпочтительным было бы применение сортировки по месту, при которой не нужно было бы копировать элементы из одного массива в другой. Иначе говоря, нельзя ли преобразовать существующий массив в сортирующее дерево, применив к нему свойство пирамидальности?

Алгоритм Флойда

Роберт Флойд разработал такой достаточно интересный алгоритм, при котором время генерирования сортирующего дерева подчиняется отношению O(n), что значительно эффективнее алгоритма типа O(n log(n)) добавления элементов по одному в отдельное сортирующее дерево.

Алгоритм Флойда работает следующим образом. Процесс начинается с родительского узла самого правого дочернего узла (т.е. узла, расположенного в крайней правой позиции последнего уровня сортирующего дерева). Применим к этому родительскому узлу алгоритм просачивания. Выберем узел, расположенный на этом же уровне слева от родительского узла (конечно, он тоже будет родительским). Снова применим алгоритм просачивания. Продолжим перемещение влево, применяя алгоритм просачивания, пока не останется узлов для обработки. Перейдем к крайнему справа узлу следующего уровня. Продолжим этот же процесс перемещения справа налево, переходя от уровня к уровню, пока не будет достигнут корневой узел. С этого момента массив упорядочен в виде сортирующего дерева.

Чтобы доказать справедливость отношения O(n), предположим, что сортирующее дерево содержит 31 элемент (это сортирующее дерево будет иметь 5 заполненных уровней). На первом этапе нужно было бы выполнить обработку всех узлов четвертого уровня. Таких узлов восемь и для каждого из них потребовалось бы не более одной операции перемещения на более низкий уровень - всего таких операций требовалось бы не более восьми. На следующем этапе нужно было бы сформировать сортирующие мини-деревья на 3 уровне. Таких сортирующих деревьев четыре и для каждого требовалось бы не более двух операций понижения уровня (всего восемь). На следующем шаге потребовалось бы образовать сортирующие деревья на 2 уровне: существует три узла, которые могли бы требовать обработки, для каждого из которых может требоваться не более трех операций перемещения на более низкий уровень. Таким образом, для узлов этого уровня может потребоваться выполнение не более шести операций. Для образования сортирующего дерева на последнем шаге требуется максимум четыре операции понижения уровня. Таким образом, всего для формирования сортирующего дерева требовалось бы выполнение не более 26 операций перемещения на более низкий уровень -меньше исходного количества узлов. Если применить эти же рассуждения к сортирующему дереву с 2(^n^) - 1 узлами, выяснится, что для создания сортирующего дерева требуется не более 2(^n^) - n - 1 операций перемещения на более низкий уровень. Отсюда следует вывод о справедливости первоначального утверждения, что алгоритм Флойда является операцией типа O(n).

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Сортировка

Из книги автора

Сортировка В отличие от предыдущих версий в Проводнике Windows Vista заголовки столбцов, с помощью которых можно проводить сортировку объектов и другие действия, доступны при любом способе отображения значков.Щелчком кнопки мыши на заголовке любого столбца вы можете


Сортировка

Из книги автора

Сортировка Трудности? Это еще что такое? Однако бесплатный сыр сами знаете где. Дело в том, что, так как сами элементы в списке не хранятся, придется самим заботится о сортировке. Не удастся воспользоваться функцией CListCtrl::SortItems, бесполезно писать CompareItems и т.п. Все, что у вас


8.1.5. Сортировка массива

Из книги автора

8.1.5. Сортировка массива Самый простой способ отсортировать массив — воспользоваться встроенным методом sort:words = %w(the quick brown fox)list = words.sort # ["brown", "fox", "quick", "the"]# Или отсортировать на месте:words.sort!       # ["brown", "fox", "quick", "the"]Здесь предполагается, что все элементы массива сравнимы


8.2.10. Сортировка хэша

Из книги автора

8.2.10. Сортировка хэша Хэши по природе своей не упорядочены ни по ключам, ни по значениям. Чтобы отсортировать хэш, Ruby преобразует его в массив, который затем сортирует. Понятно, что и результатом является массив.names = {"Jack"=>"Ruby","Monty"=>"Python",         "Blaise"=>"Pascal", "Minnie"=>"Perl"} list =


7.6. Сортировка диапазона

Из книги автора

7.6. Сортировка диапазона ПроблемаИмеется диапазон элементов, которые требуется отсортировать.РешениеДля сортировки диапазонов имеется целый набор алгоритмов. Можно выполнить обычную сортировку (в восходящем или нисходящем порядке) с помощью sort, определенного в


Сортировка данных

Из книги автора

Сортировка данных Любые данные вы можете отсортировать по алфавиту (если сортируемые ячейки содержат текст), по возрастанию или убыванию и даже по цвету ячейки и шрифта. Чтобы рассмотреть примеры сортировки данных, приведенные в этом разделе, вам нужно создать таблицу.


СОРТИРОВКА ЧИСЕЛ

Из книги автора

СОРТИРОВКА ЧИСЕЛ      Одним из наиболее распространенных тестов для машин является сортировка. Мы хотим разработать программу для сортировки целых чисел. Снова применим принцип черного ящика и подумаем в терминах ввода и вывода. Наш общий замысел, показанный на рис. 10.4,


Сортировка данных

Из книги автора

Сортировка данных      Рассмотрим еще раз функцию main( ):  main(  ){int numbers[MAXSIZE]; /* массив для ввода */int size;     /* количество введенных элементов */size = getarray(numbers, MAXSIZE); /* помещает ввод в массив */sort(numbers, size); /* сортировка массива */printf(numbers, size); /* печать отсортированного


Сортировка (Sort)

Из книги автора

Сортировка (Sort) template ‹class RandomAccessIterator›void sort(RandomAccessIterator first, RandomAccessIterator last);template ‹class RandomAccessIterator, class Compare›void sort(RandomAccessIterator first, RandomAccessIterator last, Compare соmр);sort сортирует элементы в диапазоне [first, last). Делается приблизительно NIogN (где N равняется last-first) сравнений в среднем. Если


Глава 5. Сортировка

Из книги автора

Глава 5. Сортировка Сортировка при повседневном программировании встречается очень часто. Когда на форме выводится поле со списком, его удобнее и легче использовать, если элементы в списке отсортированы в алфавитном порядке. Мы, как люди, при изучении данных предпочитаем


Глава 9. Очереди по приоритету и пирамидальная сортировка.

Из книги автора

Глава 9. Очереди по приоритету и пирамидальная сортировка. В главе 3 мы рассмотрели несколько очень простых структур данных. Одной из них была очередь. В эту структуру можно было добавлять элементы, а затем извлекать их в порядке поступления. При этом сохранение даты и


Сортировка

Из книги автора

Сортировка При преобразовании документа элементами xsl:for-each и xsl:apply-templates, выбранные узлы по умолчанию обрабатываются в порядке просмотра документа, который зависит от выражения, использованного в атрибуте select этих элементов. XSLT позволяет изменять этот порядок