end;

for i = 1 ton do begin;

rc,+i =ai I ri—сортированные элементы) end.

Сложность алгоритма сортировки перечислением определяется парой вложенных циклов и составляет 0(п2). Величина сложности не зависит от расположения данных в исходной последовательности flj, Oi,..., ап.

Пусть перестановка л = {щ,к2>-, ял), гдетг,- = с,- + 1./= 1, 2,..., п. Алгоритм 5.4 сортировки перечислением определяет перестановку , которая соответствует расположению а , <а , <...<а ,

исходных данных

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

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

96-

2217228

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

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

57

39""96.

2217228

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

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

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

Метод сортировкипредставлен в алгоритме 5.5, где

исходная последовательностьданных представляется

в виде дерева на смежной памяти (одномерный массив а[1..п]). В таком дереве ребра присутствуют неявно и вычисляются с помощью арифметических операций над индексами элементов массива — смежной памяти. Пример двоичного дерева показан на рис. 5.3. Корень дерева — а[1], за каждой вершиной а[к] следуют вершины a[2k] и a[2k+l]. Использование смежной памяти для представления дерева имеет и другие преимущества, которые становятся очевидными после анализа алгоритма 5.5.

-а[1].

а[2]

а[3]

л[-Ца[5]а6а[7]

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

Основу алгоритма 5.5 составляет процедура SURFACE (a[i..k]) всплытия Флойда, которая за 0(log2«) сравнений преобразует почти упорядоченное поддерево в упорядоченное. Поддерево представляется на одномерном массиве a[i..k], рис.5.4, где aij — корень поддерева, a[k] — максимальный элемент массива, который еще может принадлежать поддереву.

-a[ij

a[k]

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

Определим сложность процедуры SURFACE всплытия Флойда. Процедура заключается в том, что значение из корня (здесь может нарушаться условие упорядоченности) всплывает по направлению к листьям (последний уровень вершин в дереве) до тех пор, пока дерево не преобразуется в упорядоченное. Во время всплытия на каждом уровне выполняется конечное число С операций сравнения элементов. Если положить, что высота дерева (число уровней в дереве) равна Л, то сложность одного всплытия составите • h = 0(h). Высота h регулярного двоичного дерева из и вершин легко находится из соотношения п < 2° + 21 +...+ 2Л 1, где 2~ — количество вершин на i-м уровне дерева, i = 1, 2,..., п. Отсюда высота дерева Л = [\og2(n + 1)1. Таким образом, сложность процедуры SURFACE всплытия Флойда составляет

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

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

наибольшего (наименьшего) элемента множества при помощи

следующего применения процедуры SURFACEФлойда.

На рис. 5.5 показана полная последовательность перестановок и всплытий, которые происходят после формирования из исходно-

4—2697