Алгоритм выбора

BFPRT-Алгоритм предназначен для эффективного поиска i-того элемента в неотсортированном списке. Назван в честь своих изобретателей: Manual Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest и Robert Endre Tarjan. Используется при достаточно длинном списке элементов, свыше 800 элементов.

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

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

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

Особенности

При каждом рекурсивном вызове, алгоритм позволяет отбросить четверть элементов.

Литература

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