8.3. Сортировка с помощью дерева

Все способы сортировок основаны на многократном просмотре массива записей и выполнении определенных операций над ними. Можно ли улучшить временные характеристики сортировок? Ответ положителен, если за единичный просмотр массива извлекать больше информации. Для этого следует сортируемый массив S представить в виде нелинейной структуры типа двоичного (бинарного) дерева D. На рисунке показан такой граф D для массива S из n<16 элементов. В кружках размещены элементы массива: 9 14 8 1 5 4 9 12 3 17 1 3. Натуральными числами, начиная от 1, сверху вниз по уровням и слева направо на одном уровне пронумерованы все вершины дерева. Эти номера (адреса) проставлены около вершин.

У бинарного дерева имеется только один корневой узел, для которого нет предшественников – родителей. Адрес корня – 1. Любой другой узел имеет только одного предшественника и одного или двух преемников – потомков. Иногда деревья изображают в виде двумерного массива с явным указанием адресов родителей и потомков для каждого узла k (k=1n). Однако на практике эти адреса лучше не хранить, а вычислять по формулам

родитель: ,

потомок слева: , потомок справа: .

Любой узел дерева может быть корнем другого дерева – поддерева, именуемого номером узла, выбранного в качестве его корня.

Описанное представление массива S в форме бинарного дерева D, используется для построения алгоритма пирамидальной сортировки. Здесь же рассмотрим родственное представление массива S и некоторой дополнительной информации для него в форме дерева. Это позволит уяснить серию бинарных или турнирных сортировок. Пусть элементы массива S размещены в узлах нижнего уровня D. Тогда отсортировать массив можно в два этапа, называемых построением исходного дерева и непосредственной сортировкой.

Этап 1. На первом шаге посредством n/2 сравнений пар элементов массива S определяется элемент с меньшим значением, который переводится на следующий уровень и становится общим родителем пары. На втором шаге за не более, чем n/4+1 сравнений, находятся наименьшие элементы для родительских пар и переводятся на следующий уровень родителей для родительских пар и т.д. В общем случае построение дерева выбора, корнем которого окажется наименьший элемент массива, потребуется всего n-1 сравнений.

Этап 2. Элемент с наименьшим значением , поднявшийся до корня дерева, объявляется очередным элементом отсортированного массива. Производится спуск по пути, им обозначенному при подъеме вверх по дереву. При наличии нескольких таких путей вниз предпочтение отдается тем, которые включают потомков слева. Элемент с наименьшим значением  на нижнем уровне D исключается (=) и производится дополнительное сравнение элементов для пройденного пути наверх. При э том в корень дерева выходит следующий элемент с наименьшим значением и т.д. (см. рис.). После n-кратного выполнения этапа дерево D будет состоять из значений , процесс сортировки на этом завершается. Для однократного прохода этапа требуется выполнить log₂ n сравнений.

Общая трудоемкость турнирной сортировки составляет O(n log₂ n), операций. Алгоритмы этого типа сортировки отличаются способом представления исходной и сопутствующей информации, объемом дополнительной памяти и т.п.