Рандомизированный алгоритм множественного выбора

Пусть заданы множество $S$, состоящее из $n$ элементов линейно упорядоченного множества, и множество $K=\{k_1,k_2,\dots,k_r\}$ различных положительных целых чисел, $1\leq k_1<k_2<\ldots<k_r<n$. Задача множественного выбора состоит в нахождении $k_i$-х наименьших элементов множества $S$ для всех $i=1,\dots,r$. В работе предложен эффективный рандомизированный алгоритм, решающий эту задачу за время $O(n\ln r)$ с вероятностью, не меньшей $1-cn^{-1}$, где $c$ – положительная постоянная. Алгоритм можно рассматривать как единообразный подход к задачам рандомизированного выбора, множественного выбора и сортировки.