Методы программирования. Громов Ю.Ю - 77 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

77
Если N является точным значением 2
n
, то можно организовать вы-
бор n-й степени. При этом файл разбивают на две группы по 2
n–1
элемен-
тов, каждую группу – на две подгруппы по 2
n–2
элементов и т.д. Таким
образом, выбор n-й степени основан на структуре бинарного дерева, его
называют также выбором из дерева. Время его работы пропорционально
значению N logN.
На рисунках 28 – 30 наши 16 чисел сортируются посредством выбо-
ра из дерева.
Рис. 28. Исходная конфигурация дерева
Рис. 29. Дерево после вывода элемента 908
Рис. 30. Дерево после вывода элементов
908, 897, 765, 703, 677, 653 и 612
908
908
765
512
908
653
765
503
512
908
897
653
509
677
765
503
87
512
61
908
170
897
275
653
426
154
509
612
677
765
703
897
897
765
512
897
653
765
503
512
170
897
653
509
677
765
503
87
512
61
-
∝
170
897
275
653
426
154
509
612
677
765
703
512
512
509
512
275
509
-
∝
503
512
170
275
426
509
-
∝
-
∝
503
87
512
61
-
∝
170
-
∝
275
-
∝
426
154
509
-
∝
-
∝
-
∝
-
∝

Страницы