304
правки
Изменения
м
Мы разберем в данном данном случае, поиск рассекающего элемента.
Проведем анализ рассекающего элемента. На рисунке обозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. В каждой области по <tex> 8 </tex> элементов, всего же в массиве <tex> 25 </tex>, то есть мы получили хорошее (то есть соответствующее нашему утверждению) разбиение массива относительно опорного элемента, так как <tex> 8 > </tex> <tex>\frac{3 \cdot 25}{10}</tex>. Теперь докажем, что алгоритм также хорошо выбирает опорный элемент и в общем случае.
→Описание алгоритма
== Описание алгоритма ==
#Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n</tex> <tex>\bmod</tex> <tex> 5</tex> элементов. Эта группа может оказаться пустой при <tex>n</tex> кратных <tex>5</tex>.
#Сначала сортируется каждая группа, затем выбираем медиану в из каждой из этих группгруппы выбирается медиана.#Путем рекурсивного вызова шага 1 определяется медиана <tex>x</tex> из множества медиан(верхняя медиана в случае чётного количества), найденных на втором шаге. Где Найденный элемент массива <tex>x</tex> — используется как рассекающий элемент, (за <tex>i</tex> — обозначим его индекс рассекающего элемента. Если медиан окажется четное количество, то на место рассекающего элемента будут претендовать две медианы, переменной <tex>x</tex> будет присвоено значение большей из этих двух медиан).#Делим массив Массив делится относительно рассекающего элемента <tex>x</tex>. Все элементы меньшие <tex>x</tex> будут находиться левее <tex>x</tex> в массиве и будут иметь меньший индекс и наоборот, если элементы больше <tex>x</tex>.#Если <tex>i</tex> <tex>=</tex> <tex>k</tex>, то возвращается значение <tex>x</tex>. Иначе вызывается запускается рекурсивно шаг 1, и выполняется поиск элемента в одной из частей массива: <tex>k</tex>-го в порядке возрастания элемента ой статистики в левой части массива,если при <tex>i</tex> <tex><k</tex> или <tex>(k- i - 1)</tex>, или -ой статистики в правой части, если при <tex>i</tex> <tex>></tex> <tex>k</tex>.
=== Пример работы алгоритма ===
Рассмотрим работу алгоритма на массиве из <tex> 25 </tex> элементов, обозначенных кружками.
[[Файл:поиск2.png| 300px]]
Cначала определим нижнюю границу для количества элементов, превышающих по величине рассекающий элемент <tex>x</tex>. В общем случае как минимум половина медиан, найденных на втором шаге, больше или равны медианы медиан <tex>x</tex>. Таким образом, как минимум <tex>n</tex> <tex>/</tex> <tex>10</tex> групп содержат по <tex>3</tex> превышающих величину <tex>x</tex>, за исключение группы, в которой меньше <tex>5</tex> элементов и ещё одной группы, содержащей сам элемент <tex>x</tex>. Таким образом получаем, что количество элементов больших <tex>x</tex>, не менее <tex>\frac{3n}{10}</tex>.
