Сортировка методом турнира с выбыванием

Приведем другой алгоритм сортировки, основанный на использовании бинарных деревьев. Данный метод получил название турнира с выбыванием. Пусть имеется исходный массив 10, 20, 3, 1, 5, 0, 4, 8. Сортировка начинается с создания листьев дерева. В качестве листьев бинарного дерева создаются узлы, в которых записаны значения элементов исходного массива. Дерево строится от листьев к корню. Для двух соседних узлов строится общий предок, до тех пор, пока не будет создан корень. В узел-предок заносится значение, являющееся наименьшим из значений в узлах-потомках.

В результате построения такого дерева наименьший элемент попадает сразу в корень. Далее начинается извлечение элементов из дерева. Извлекается значение из корня. Данное значение является первым элементом в результирующем массиве. Извлеченное значение помещается в отсортированный массив и заменяется в дереве на специальный символ.

После этого происходит повторное занесение значений в родительские элементы от листьев к корню. При сравнениях специальный символ считается большим по отношению к любому другому значению. После повторного заполнения из корня извлекается очередной элемент и итерация повторяется. Извлечения элементов продолжаются до тех пор, пока в дереве не останутся одни специальные символы. В результате получим отсортированный массив 0, 1, 3, 4, 5, 8, 10, 20. Описанный алгоритм иллюстрируют рис. 7.16-7.19.

Рис. 7.16. Построение дерева сортировки.

Рис. 7.17. Замена извлекаемого элемента на специальный символ.

Рис. 7.18. Повторное заполнение дерева сортировки.

Рис. 7.19. Извлечения элементов из дерева сортировки.