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

         

Выбор


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

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

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

-ом шаге равно
, что приводит к общему числу сравнений имен

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


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

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

-го наибольшего имени, чего можно добиться, используя механизм турнира с выбыванием. Суть его такова: сравниваются
, затем сравниваются "победители" (то есть большие имена) этих сравнений и т.д.; эта процедура для
показана на рис. 15.1.

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

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

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

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



Заметим, что в пирамиде наибольшее имя должно находиться в корне и, таким образом, всегда в первой позиции массива, представляющего пирамиду. Обмен местами первого имени с
-м помещает наибольшее имя в его правильную позицию, но нарушает свойство пирамидальности в первых
именах. Если мы можем сначала построить пирамиду, а затем эффективно восстановить ее, то все в порядке, так как тогда можно производить сортировку следующим образом: построить пирамиду из
,



Это общее описание пирамидальной сортировки.


Рис. 15.1.  Использование турнира с выбыванием для отыскания наибольшего имени.Путь наибольшего имени показан жирной линией


Рис. 15.2.  Отыскание второго наибольшего имени путем замены наибольшего имени на
. Проведение повторного сравнения имен, побежденных наибольшим именем

Процедура RESTORE
восстановления пирамиды из последовательности
в предположении, что все поддеревья суть пирамиды, такова:



Переписывая это итеративным способом и дополняя деталями, мы получим алгоритм 15.2.


Алгоритм 15.2.Восстановление пирамиды из дерева, поддеревья которого суть пирамиды


Рис. 15.3.  Пирамида, содержащая 12 имен


Алгоритм 15.3.Пирамидальная сортировка


Содержание раздела