Структуры и алгоритмы обработки данных


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


Приведем другой алгоритм сортировки, основанный на использовании бинарных деревьев. Данный метод получил название турнира с выбыванием. Пусть мы имеем исходный массив

10, 20, 3, 1, 5, 0, 4, 8

Сортировка начинается с создания листьев дерева. В качестве листьев бинарного дерева создаются узлы, в которых записаны значения элементов исходного массива.

Дерево строится от листьев к корню. Для двух соседних узлов строится общий предок, до тех пор, пока не будет создан корень. В узел-предок заносится значение, являющееся наименьшим из значений в узлах-потомках.

pic4_10.gif (3105 bytes)

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

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

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

После повторного заполнения из корня извлекается очередной элемент и итерация повторяется. Извлечения элементов продолжаются до тех пор, пока в дереве не останутся одни специальные символы.

pic4_11.gif (3058 bytes)

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

pic4_12.gif (3094 bytes)

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

pic4_13.gif (6363 bytes)

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

В результате получим отсортированный массив

0, 1, 3, 4, 5, 8, 10, 20




Начало  Назад  Вперед



Книжный магазин