55
правок
Изменения
Нет описания правки
2.Сначала сортируется каждая группа, затем выбираем медиану в каждой из этих групп.
3.Путем рекурсивного вызова шага 1 определяется медиана <tex>x</tex> из множества медиан, найденных на втором шаге. <tex>x</tex> - рассекающий элемент, <tex>i</tex> - индекс рассекающего элемента.(Если медиан окажется четное количество, то переменной <tex>x</tex> будет присвоено значение нижней верхней медианы.)
4.Делим массив относительно рассекающего элемента <tex>x</tex>. Все элементы меньшие <tex>x</tex> будут находиться левее <tex>x</tex> в массиве и будут иметь меньший индекс и наоборот,если элементы больше <tex>x</tex>.
Как будет доказано ниже, время работы алгоритма в наихудшем случае равно <tex>O(n)</tex>. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива, так как чисел, которые меньше рассекающего элемента не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве.
===Пример===
На вход подается массив, разобьем элементы на группы по 5.
Отсортируем элементы каждой группы и выберем медианы. Вызовемся рекурсивно от медиан.
[[Файл:BFPRT2.png| 300px]]
Разобьем на группы по 5 медианы.
Отсортируем элементы каждой группы и выберем медианы
[[Файл:BFPRT.png| 80px]]
Выберем медианы медиан. В итоге мы получили один элемент равный <tex>40</tex>. Это и есть рассекающий элемент.
