В информатике алгоритм выбора — это алгоритм для нахождения k -го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой ). Частными случаями этого алгоритма являются нахождение минимального элемента , максимального элемента и медианы . Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O( n ).

Выбор с помощью сортировки

Задачу выбора можно свести к сортировке . Можно упорядочить массив, а затем взять нужный по счёту элемент. Это эффективно в том случае, когда выбор нужно делать многократно: тогда можно отсортировать массив за O( n log n ) и затем выбирать из него элементы. Однако если выбор нужно произвести однократно, этот алгоритм может оказаться неоправданно долгим.

Линейный алгоритм для нахождения минимума (максимума)

Способ за линейное время найти минимум (максимум) в массиве:

• Изначально присвоить ${\displaystyle min=a[0];}$
• Для каждого элемента ${\displaystyle a[i]}$ выполнить: если ${\displaystyle min>a[i]}$ , присвоить ${\displaystyle min=a[i]}$ .

Линейный в среднем алгоритм для нахождения k -й порядковой статистики

Существует алгоритм для нахождения k -й порядковой статистики, основанный на алгоритме быстрой сортировки и работающий за O( n ) в среднем.

Идея алгоритма заключается в том, что массив разбивается на две части относительно случайно (равновероятно) выбранного элемента — в одну часть попадают элементы, меньшие, чем выбранный, в другую — остальные (эта операция выполняется за ${\displaystyle O(n)}$ , по её окончании выбранный элемент находится в позиции ${\displaystyle j}$ ). Если в первой части оказалось ровно ${\displaystyle k-1}$ элементов ( ${\displaystyle j=k}$ ), то выбранный элемент является искомым, если ${\displaystyle j>k}$ , то алгоритм выполняется рекурсивно для первой части массива, иначе — для второй (в последнем случае для следующей итерации от ${\displaystyle k}$ отнимается ${\displaystyle j}$ ). Рекурсивные вызовы приводят к экспоненциально уменьшающемуся с каждой итерацией размеру обрабатываемого массива, и по этой причине время выполнения алгоритма составляет ${\displaystyle O(n)}$ .

Алгоритм BFPRT (линейный детерминированный)

BFPRT-Алгоритм позволяет найти k -ю порядковую статистику гарантированно за O( n ). Назван в честь своих изобретателей: Manual B lum, Robert W. F loyd, Vaughan R. P ratt, Ronald L. R ivest и Robert Endre T arjan. Используется при достаточно длинном списке элементов, свыше 800 элементов.

Принцип действия

Ввод: число ${\displaystyle i}$ , обозначающее ${\displaystyle i}$ -й элемент.

1. Список делится на подмножества элементов, по 5 элементов в каждом (кроме последнего подмножества). Число элементов в подмножествах может превышать 5 и должно быть в любом случае нечётным. Однако если делить список на подмножества из 3 элементов, время работы не будет линейным.
2. Каждое подмножество сортируется с помощью подходящего алгоритма сортировки.
3. Пусть ${\displaystyle S}$ — множество медиан, образовавшихся в подмножествах после сортировки. Рекурсивно находится медиана в ${\displaystyle S}$ — медиана медиан. Назовем её ${\displaystyle s}$ .
   • Результирующая после 3 шага структура, имеет следующую особенность:
     • Четверть всех элементов в любом случае имеет ключ ${\displaystyle <s}$ . (Подмножество множества ${\displaystyle S_{1}}$ )
     • Четверть всех элементов в любом случае имеет ключ ${\displaystyle >s}$ . (Подмножество множества ${\displaystyle S_{2}}$ )
4. Теперь список разбивается относительно медианы s на 2 подмножества ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$ . При этом нужно сравнить с s только половину всех элементов, так как две четверти элементов уже отсортированы относительно s. В результате каждое из подмножеств ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$ содержит максимально 3/4 всех элементов (минимально — 1/4 всех элементов).
5. Если:
   • ${\displaystyle i=|S_{1}|+1}$ , то искомый элемент найден — это медиана медиан ${\displaystyle s}$
   • ${\displaystyle i\leq |S_{1}|}$ , то алгоритм вызывается рекурсивно на множестве ${\displaystyle S_{1}}$
   • в любом другом случае, алгоритм вызывается рекурсивно на множестве ${\displaystyle S_{2}}$

Гарантированное время работы

При каждом рекурсивном вызове , алгоритм позволяет отбросить минимум четверть всех элементов. Это обеспечивает верхнюю оценку на гарантированное линейное время работы для детерминированного алгоритма , так как оно выражается рекуррентным соотношением ${\displaystyle T(n)=O(n)+T\left({\frac {n}{5}}\right)+T\left({{\frac {7}{10}}n}\right)}$ . В общем случае, если подмножества имеют размер ${\displaystyle 2k+1}$ , время работы выражается как ${\displaystyle T(n)=O(n)+T\left({\frac {n}{2k+1}}\right)+T\left({{\frac {3k+1}{4k+2}}n}\right)}$ .

Литература

• Volker Heun. Основные Алгоритмы = Grundlegende Algorithmen. — 1-е изд. — Мюнхен: Vieweg Verlag, 2000. — С. 86. — ISBN 3-528-03140-9 .
• (англ.)