Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 5.4. Сортировка всплытием ФлойдаВсе ранее упомянутые методы сортировки последовательности
Рис. 5.1. Пример упорядоченного двоичного дерева Значение в каждой его вершине не меньше, чем значение в его дочерних вершинах. Двоичное дерево называется частично упорядоченным, если свойство упорядоченности выполняется для каждой из его вершин, однако для корня это свойство нарушается. Пример частично упорядоченного дерева приведен на рис. 5.2.
Рис. 5.2. Пример частично упорядоченного двоичного дерева Интересно отметить, что в ранее рассмотренных методах сортировки сложности Метод сортировки Флойда представлен в алгоритме 5.5, где исходная последовательность
Рис. 5.3. Пример двоичного дерева на смежной памяти Основу алгоритма 5.5 составляет процедура
Рис. 5.4. Двоичное поддерево на смежной памяти Определим сложность процедуры SURFACE всплытия Флойда. Процедура заключается в том, что значение из корня (здесь может нарушаться условие упорядоченности) всплывает по направлению к листьям (последний уровень вершин в дереве) до тех пор, пока дерево не преобразуется в упорядоченное. Во время всплытия на каждом уровне выполняется конечное число С операций сравнения элементов. Если положить, что высота дерева (число уровней в дереве) равна Рассмотренная процедура SURFACE всплытия Флойда позволяет в почти упорядоченном дереве найти наибольший (наименьший) элемент за число сравнений После того как дерево упорядочено, наибольший (наименьший) элемент оказывается в его корне. По алгоритму 5.5 найденный элемент меняют местами с самым последним листом в дереве (последний элемент рассматриваемого массива), дерево уменьшается на одну вершину и все готово для определения нового наибольшего (наименьшего) элемента множества при помощи следующего применения процедуры SURFACE всплытия Флойда. На рис. 5.5 показана полная последовательность перестановок и всплытий, которые происходят после формирования из исходного множества почти упорядоченного дерева и вплоть до того, как в этом дереве останется всего одна вершина, а исходное множество окажется отсортированным. Рис. 5.5. (см. скан) Пример сортировки чисел 18,4,56,65,37,63,66 методом Флойда Алгоритм 5.5. Сортировка всплытием Флойда сложности Сортировка по возрастанию (см. скан) (см. скан) (см. скан) Оценим общую сложность алгоритма сортировки данных рассматриваемым методом. Процедура SURFACE всплытия Флойда выполняется Это лучшая оценка, на что вообще можно надеяться при сортировках, в основу которых положены сравнения данных. Действительно, число возможных перестановок из элементов Задача. Длина объединения отрезков. Текстовый файл содержит целые числа: Пример файла исходных данных:
Пример файла выходных данных:
Решение. Алгоритм 5.6 решения задачи основывается на предварительной сортировке абсцисс Алгоритм (см. скан) (см. скан)
|
1 |
Оглавление
|