Лекція 6 6.1.1. Метод вибірки з дерева

МЕТОДИ СОРТУВАННЯ НА ДЕРЕВАХ

Сортування на деревах

Розглянемо два методи сортування, які використовують дерево­подібне зображення початкової таблиці: простий і складний. Простий метод подібний до класуалгоритмів вибірки, складний - спирається на пірамідальне зображення дерева, його називають також по імені автора - алгоритмом Флойда.

6.1.1. Метод вибірки з дерева /алгоритм Н /.

Послідовність чисел розбивається на пари, які об‘єднуються за принципом «син-батько». Батьком з двох синів стає найбільше число. Процес повторюється, доки не буде виділене одне число, найбільше, яке стане корнем утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок (син). Число, що попало в корінь замінюється на безмежність. Процес повторюється для знаходження наступного найбільшого числа і т.д. З рис. 6.1 видно, що задана послідовність буде впорядкована у низхід­ному порядку за 10-1=9 кроків.

Сумарний час виконання такого сортування приблизно пропорційний величині п log₂ n. Існує декілька модифікацій цього алгоритму, які скорочують цей час.

Рис.6.1. Схема сортування методом вибірки з дерева:

а - послідовність з десяти чисел для відбору першого найбільшого елемента;

б - вибір другого найбільшого елемента.