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

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

можно найти

-е из наибольших в порядке убывания? Задача, очевидно, симметрична: отыскание

-го наибольшего (

-го наименьшего) имени можно осуществить, используя алгоритм отыскания

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

эквивалентно отысканию наименьшего имени

; отыскание второго наибольшего имени

эквивалентно отысканию второго наименьшего

и т.д.

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

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

сравнений имен независимо от значений

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

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

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

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

наибольших имен.

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