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



             

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


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

x_1,x_2,\ldots,x_n
можно найти
k
-е из наибольших в порядке убывания? Задача, очевидно, симметрична: отыскание
(n - k + 1)
-го наибольшего (
k
-го наименьшего) имени можно осуществить, используя алгоритм отыскания
k
-го наибольшего, но меняя местами действия, предпринимаемые при результатах < и >сравнения имен. Таким образом, отыскание наибольшего имени
(k = 1)
эквивалентно отысканию наименьшего имени
(k = n)
; отыскание второго наибольшего имени
(k = 2)
эквивалентно отысканию второго наименьшего
(k = n - 1)
и т.д.

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

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

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

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

 (n - 1) + (n - 2) + \ldots + (n - k) = kn - \frac{{k(k + 1)}}{2}

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

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




Содержание  Назад  Вперед