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

Действия метода отражают процесс разыгрывания некоторого турнира, где его участники состязаются друг с другом для определения наилучшего игрока. Эта сортировка также называется сортировкой посредством выбора из дерева. Рассмотрим некоторый турнир в виде дерева [3].

Такое дерево можно понимать следующим образом: Кейс играла в турнире с Гейл и проиграла, т.е. победила Гейл и ее имя помещается в узел дерева и т.д. То есть на представленном дереве показан турнир, в котором победила Гейл. А кто занял 2-е место? А 3-е место? Решение на основе просмотра дерева от листьев к корню позволяет сделать вывод, что 2-е место заняла Пэт, а Джордж с Фрэнком поделили 3-е место, т.е. Гейл выиграла 3 игры, а Пэт выиграла 2 игры, а Джорд с Фрэнком выиграли по 1 игре.

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

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

Пример. Задана последовательность чисел: 25, 57, 48, 37, 12, 92, 86, 33. Отсортировать ее методом «турнира с выбыванием».

Решение. Начинаем формировать дерево с листьев:

2 этап

и т.д.