Комбинаторные алгоритмы для программистов



             

Выбор


В сортировке посредством выбора основная идея состоит в том, чтобы идти по шагам

i = 1,2,\ldots,n
, находя
i
-е наибольшее (наименьшее) имя и помещая его на его место на
i
-ом шаге. Простейшая форма сортировки выбором представлена алгоритмом 15.1:
i
-е наибольшее имя находится очевидным способом просмотром оставшихся
n - i + 1

имен. Число сравнений имен на

i
-ом шаге равно
n - i
, что приводит к общему числу сравнений имен
(n - 1) + (n - 2) + \ldots + 1 = \frac{1} {2}n(n - 1)

независимо от входа, поэтому ясно, что это не очень хороший способ сортировки.

Алгоритм 15.1. Простая сортировка выбором

Алгоритм 15.1. Простая сортировка выбором

Несмотря на неэффективность алгоритма 15.1, идея выбора может привести и к эффективному алгоритму сортировки. Весь вопрос в том, чтобы найти более эффективный метод определения

i
-го наибольшего имени, чего можно добиться, используя механизм турнира с выбыванием. Суть его такова: сравниваются
x_1 :x_2,x_3 :x_4,x_5 :x_6,\ldots,x_{n - 1} :x_n
, затем сравниваются "победители" (то есть большие имена) этих сравнений и т.д.; эта процедура для
n = 16
показана на рис. 15.1.

Заметим, что для определения наибольшего имени этот процесс требует

n - 1
сравнений имен; но, определив наибольшее имя, мы обладаем большим объемом информации о втором по величине (в порядке убывания) имени: оно должно быть одним из тех, которые "потерпели поражение" от наибольшего имени. Таким образом, второе по величине имя теперь можно определить, заменяя наибольшее имя на
- \infty
и вновь осуществляя сравнение вдоль пути от наибольшего имени к корню. На рис. 15.2 эта процедура показана для дерева из рис. 15.1.

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

h
, в котором все листья находятся на расстоянии
h
или
h - 1
от корня и все потомки узла меньше его самого; кроме того, в нем все листья уровня максимально смещены влево. На рис. 15.3 показано множество имен, организованных в виде пирамиды. Чтобы получить удобное линейное представление дерева, пирамиду можно хранить по уровням в одномерном массиве: сыновья имени из
i
-ой позиции есть имена в позициях
2i
и
2i + 1
.


Содержание    Вперед