Выбор
В сортировке посредством выбора основная идея состоит в том, чтобы идти по шагам
, находя
-е наибольшее (наименьшее) имя и помещая его на его место на
-ом шаге. Простейшая форма сортировки выбором представлена алгоритмом 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.Пирамидальная сортировка
Содержание раздела
