Введение

Алгоритм для k-го наименьшего элемента в массиве

В информатике quickselect — это алгоритм выбора для поиска k-го наименьшего элемента в неупорядоченном списке, также известный как k-я порядковая статистика. Как и связанный с ним алгоритм быстрой сортировки, он был разработан Тони Хоаром и поэтому также известен как алгоритм выбора Хоара. Как и быстрая сортировка, он эффективен на практике и имеет хорошую среднюю производительность, но плохую производительность в худшем случае. Quickselect и его варианты — это алгоритмы выбора, наиболее часто используемые в эффективных реализациях в реальном мире. Quickselect использует тот же общий подход, что и быстрая сортировка, выбирая один элемент в качестве опорного и разделяя данные на две части в зависимости от того, меньше они опорного элемента или больше. Однако, в отличие от быстрой сортировки, где рекурсия выполняется для обеих частей, quickselect рекурсивно обрабатывает только одну часть — ту, где находится искомый элемент. Это снижает среднюю сложность с O(n^2) до O(n), при худшем случае O(n^2). Как и быстрая сортировка, quickselect обычно реализуется как алгоритм "на месте", и помимо выбора k-го элемента, он также частично сортирует данные. Подробное обсуждение связи с сортировкой см. в статье "Алгоритм выбора".

Временная сложность

Как и у быстрой сортировки, у алгоритма quickselect хорошая средняя производительность, но она чувствительна к выбору опорного элемента. Если опорные элементы выбираются удачно, то есть такие, которые последовательно уменьшают область поиска на определенную долю, то размер области поиска уменьшается экспоненциально, и, используя индукцию (или суммирование геометрической прогрессии), можно увидеть, что производительность линейна, поскольку каждый шаг выполняется за линейное время, а общее время пропорционально этому (в зависимости от скорости уменьшения области поиска). Однако, если последовательно выбираются неудачные опорные элементы, например, уменьшающие область поиска всего на один элемент за раз, то производительность в худшем случае становится квадратичной. Это происходит, например, при поиске максимального элемента в отсортированном наборе, используя первый элемент в качестве опорного. Однако для случайно выбранных опорных элементов этот худший случай крайне маловероятен: вероятность выполнения более чем сравнений, для любой достаточно большой константы , является сверхэкспоненциально малой функцией от .

Варианты

Самым простым решением является выбор случайного опорного элемента, что обеспечивает почти гарантированное линейное время работы. Детерминированно можно использовать стратегию «медиана из трёх» (как в быстрой сортировке), которая обеспечивает линейную производительность на частично отсортированных данных, что часто встречается на практике. Однако специально подобранные последовательности всё ещё могут привести к сложности в худшем случае; Дэвид Муссер описал последовательность, названную «убийца медианы из трёх», которая позволяет атаковать эту стратегию и послужила одной из мотиваций для разработки его алгоритма интроселекции. Можно гарантировать линейную производительность даже в худшем случае, используя более сложную стратегию выбора опорного элемента; это реализовано в алгоритме «медиана медиан». Однако вычислительные затраты на определение опорного элемента высоки, поэтому на практике он обычно не используется. Можно комбинировать базовый алгоритм быстрой выборки с алгоритмом «медиана медиан» в качестве резервного варианта, чтобы обеспечить как быструю среднюю производительность, так и линейную производительность в худшем случае; это делается в интроселекции. Более точные вычисления средней временной сложности дают худший случай для случайных опорных элементов (в случае медианы; другие значения k работают быстрее). Постоянный множитель можно улучшить до 3/2, используя более сложную стратегию выбора опорного элемента, что приводит к алгоритму Флойда — Ривеста, который имеет среднюю сложность для медианы, а другие значения k работают быстрее.