Поиск k-ой порядковой статистики за линейное время

Историческая справка

Алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна (BFPRT-алгоритм) создан Мануэлем Блюмом(Manuel Blum), Робертом Флойдом(Robert Floyd), Воганом Рональдом Праттом(Vaughan Ronald Pratt), Роном Ривестом(Ron Rivest) и Рональдом Тарьяном(Robert Tarjan) в 1973 году.

Описание алгоритма

Разбиваем наш массив на группы по 5 элементов(на самом деле можно разбивать и на другое нечетное количество элементов больших 5). Затем в каждой группе находим средний элемент(медиану), это можно сделать любой сортировкой. И запустить рекурсивно данный алгоритм от медиан. Тем самым мы найдем средний элемент среди медиан, то есть медиану медиан. Эту медиана медиан выберем рассекающим элементом для поиска [math]k[/math]-го элемента. Далее простыми обменами получаем слева от рассекающего элемента числа меньшие него, а справа числа больше рассекающего элемента или равные ему. И запускаем нашу функцию от той части массива в котором будет лежать [math]k[/math]-й элемент.

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

[math]T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn [/math] Тогда покажем, что для всех [math] n [/math] выполняется неравенство [math]T(n) \le 10Cn [/math]. Докажем по индукции

1. Очевидно, что для малых [math] n [/math] выполняется неравенство [math]T(n) \le 10Cn [/math]
2. Тогда по предположению индукции [math]T(\frac{n}{5}) \le 10C(\frac{n}{5}) = 2Cn[/math] и [math] T(\frac{10n}{7}) \le 10C(\frac{7n}{10}) = 7Cn[/math], тогда

[math]T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \le 10Cn[/math]