МЕТОДИ СОРТУВАННЯ НА ДЕРЕВАХ
Сортування на деревах
Розглянемо два методи сортування, які використовують деревоподібне зображення початкової таблиці: простий і складний. Простий метод подібний до класуалгоритмів вибірки, складний - спирається на пірамідальне зображення дерева, його називають також по імені автора - алгоритмом Флойда.
6.1.1. Метод вибірки з дерева /алгоритм Н /.
Послідовність чисел розбивається на пари, які об‘єднуються за принципом «син-батько». Батьком з двох синів стає найбільше число. Процес повторюється, доки не буде виділене одне число, найбільше, яке стане корнем утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок (син). Число, що попало в корінь замінюється на безмежність. Процес повторюється для знаходження наступного найбільшого числа і т.д. З рис. 6.1 видно, що задана послідовність буде впорядкована у низхідному порядку за 10-1=9 кроків.
Сумарний час виконання такого сортування приблизно пропорційний величині п log2 n. Існує декілька модифікацій цього алгоритму, які скорочують цей час.
Рис.6.1. Схема сортування методом вибірки з дерева:
а - послідовність з десяти чисел для відбору першого найбільшого елемента;
б - вибір другого найбільшого елемента.