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