Изменения

==Идея алгоритма==

Этот алгоритм является модификацией алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]]. Важное отличие заключается в том, что время работы алгоритма в наихудшем случае — <tex>O(n)</tex>, где <tex>n</tex> — количество элементов в множестве. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex>\frac{3n}{10}</tex>. Элементов же больших опорного элемента, также не менее <tex>\frac{3n}{10}</tex>. Благодаря этому алгоритм работает за линейное время в любом случае.