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

         

Частичная сортировка (выбор)


Как при данных именах

можно найти
-е из наибольших в порядке убывания? Задача, очевидно, симметрична: отыскание
-го наибольшего (
-го наименьшего) имени можно осуществить, используя алгоритм отыскания
-го наибольшего, но меняя местами действия, предпринимаемые при результатах < и >сравнения имен. Таким образом, отыскание наибольшего имени
эквивалентно отысканию наименьшего имени
; отыскание второго наибольшего имени
эквивалентно отысканию второго наименьшего
и т.д.

Конечно, все перечисленные варианты задачи выбора можно решить, используя любой из методов полной сортировки имен и затем тривиально обращаясь к

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

При использовании алгоритма сортировки для выбора наиболее подходящим будет один из алгоритмов, основанных на выборе: либо простая сортировка выбором (алгоритм 15.1) либо пирамидальная сортировка (алгоритм 15.3). В каждом случае мы можем остановиться после того, как выполнены первые

шагов. Для простой сортировки выбором это означает использование

сравнений имен, а для пирамидальной — использование

сравнений имен. В обоих случаях мы получаем больше информации, чем нужно, потому что мы полностью определяем порядок
наибольших имен.



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