infa_1 / 26.Турнирная и пирамидальная сортировка
..doc26. Турнирная и пирамидная сортировка
1. Турнирная сортировка
Элементы исходного множества представляются листьями дерева. Их попарное сравнение позволяет определить максимальный элемент. При этом производится попарное сравнение вершин дерева снизу вверх. А найденный максимальный элемент помещается в результирующее множество.
2. Пирамидная сортировка
Построение пирамидального дерева означает создание бинарного дерева, обладающего тремя свойствами:
1) завершением каждой триады является элемент с большим весом
2) листья бинарного дерева располагаются в одном уровне или в двух соседних
3) листья нижнего уровня левее листьев нижнего уровня
При сортировке в ходе преобразования элементы триад уравниваются дважды, при этом элемент с большим весом переходит вверх, с меньшим вниз.