BFPRT-Алгоритм

BFPRT-Алгоритм предназначен для эффективного поиска i-того по величине элемента в неотсортированном списке (т.е. находит элемент, оказавшийся бы на 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$.
   • Результирующая после 3 шага структура, имеет следующую особенность:
     • Четверть всех элементов в любом случае имеет ключ $< s$.
     • Четверть всех элементов в любом случае имеет ключ $> s$.
4. Теперь множество S сортируется относительно медиана s на 2 подмножества $S_1$ и $S_2$. При этом нужно сравнить с s только половину всех элементов, так как две четверти элементов уже отсортированы относительно s. В результате каждое из подмножеств $S_1$ и $S_2$ содержит максимально 3/4 всех элементов (минимально - 1/4 всех элементов).
5. Если:
   • $i = |S_1| + 1$, то искомый элемент найден - это медиан медианов $s$
   • $i \leq |S_1|$, то алгоритм вызывается рекурсивно на множество $S_1$
   • в любом другом случае, алгоритм вызывается рекурсивно на множество $S_2$

Особенности

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

Литература

• Volker Heun Основные Алгоритмы = Grundlegende Algorithmen. — 1-е изд. — Мюнхен: Vieweg Verlag, 2000. — С. 86. — ISBN 3-528-03140-9
• Time Bounds for Selection by Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Journal of Computer and System Sciences 7,4 August 1973, 448—460  (англ.)