5.4. Сортировка всплытием Флойда

Все ранее упомянутые методы сортировки последовательности требовали сравнений порядка и «это никуда не годится». Рассмотрим один из наиболее элегантных и эффективных методов сортировки сложности предложенный Флойдом. До сих пор он остается самым оптимальным из существующих методов. В алгоритме активно используется упорядоченное двоичное дерево, пример которого представлен на рис. 5.1.

Рис. 5.1. Пример упорядоченного двоичного дерева

Значение в каждой его вершине не меньше, чем значение в его дочерних вершинах. Двоичное дерево называется частично упорядоченным, если свойство упорядоченности выполняется для каждой из его вершин, однако для корня это свойство нарушается. Пример частично упорядоченного дерева приведен на рис. 5.2.

Рис. 5.2. Пример частично упорядоченного двоичного дерева

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

Метод сортировки Флойда представлен в алгоритме 5.5, где исходная последовательность данных представляется в виде дерева на смежной памяти (одномерный массив В таком дереве ребра присутствуют неявно и вычисляются с помощью арифметических операций над индексами элементов массива — смежной памяти. Пример двоичного дерева показан на рис. 5.3. Корень дерева — за каждой вершиной следуют вершины Использование смежной памяти для представления дерева имеет и другие преимущества, которые становятся очевидными после анализа алгоритма 5.5.

Рис. 5.3. Пример двоичного дерева на смежной памяти

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

Рис. 5.4. Двоичное поддерево на смежной памяти

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

Рассмотренная процедура SURFACE всплытия Флойда позволяет в почти упорядоченном дереве найти наибольший (наименьший) элемент за число сравнений преобразуя дерево к упорядоченному виду. В результате найденный элемент будет располагаться в вершине дерева. Для сортировки же множества элементов из них по алгоритму 5.5 сначала организуется почти упорядоченное двоичное дерево при помощи повторного применения алгоритма SURFACE всплытия Флойда сначала к самым мелким его поддеревьям от листьев и затем ко все более крупным. Листья тривиально упорядочены, поэтому можно начать с минимальных поддеревьев, содержащих несколько вершин, и укрупнять их, каждый раз полностью, применяя алгоритм всплытия до тех пор, пока таким образом не будет достигнут корень дерева. Заметим, что каждое из поддеревьев, к которым применяется алгоритм всплытия, удовлетворяет условию почти упорядоченности, поскольку упорядочивание проходит от листьев к корню. Именно таким способом в алгоритме 5.5 осуществляется формирование исходного почти упорядоченного дерева.

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

исходного множества почти упорядоченного дерева и вплоть до того, как в этом дереве останется всего одна вершина, а исходное множество окажется отсортированным.

Рис. 5.5. (см. скан) Пример сортировки чисел 18,4,56,65,37,63,66 методом Флойда

Алгоритм 5.5. Сортировка всплытием Флойда сложности

Сортировка по возрастанию

(см. скан)

(см. скан)

(см. скан)

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

Это лучшая оценка, на что вообще можно надеяться при сортировках, в основу которых положены сравнения данных. Действительно, число возможных перестановок из элементов равно и только одна из них удовлетворяет условию нашей сортировки. Двоичный же поиск перестановки среди множества перестановок требует числа сравнений. Для упрощения воспользуемся формулой Стирлинга Тогда

Задача. Длина объединения отрезков. Текстовый файл содержит целые числа: Данная последовательность чисел определяет на прямой отрезков Найти длину объединения указанных отрезков. Исходные данные представлены в текстовом файле со следующей структурой. Первая строка файла: количество отрезков. Вторая, третья и т.д. строки файла содержат целые числа — границы соответствующих отрезков. Результаты расчетов длины объединения отрезков сохранить в текстовом файле.

Пример файла исходных данных:

Пример файла выходных данных:

Решение. Алгоритм 5.6 решения задачи основывается на предварительной сортировке абсцисс в массиве Создается вспомогательный массив который поддерживает после сортировки массива отношение границ отрезков: левая граница, правая граница. Вычисление завершается простым просмотром массива за линейное время. Общая сложность алгоритма определяется сложностью сортировки данных. В данном случае используется алгоритм пузырьковой сортировки сложности

Алгоритм Программа расчета длины объединения отрезков

(см. скан)

(см. скан)