Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

infa_1 / 26.Турнирная и пирамидальная сортировка

..doc
Скачиваний:
46
Добавлен:
05.06.2015
Размер:
381.95 Кб
Скачать

26. Турнирная и пирамидная сортировка

1. Турнирная сортировка

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

2. Пирамидная сортировка

Построение пирамидального дерева означает создание бинарного дерева, обладающего тремя свойствами:

1) завершением каждой триады является элемент с большим весом

2) листья бинарного дерева располагаются в одном уровне или в двух соседних

3) листья нижнего уровня левее листьев нижнего уровня

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