Изменения

Разбиваем наш массив 1.Все <tex>n</tex> элементов входного массива разбиваются на группы по 5 элементов (на самом деле можно разбивать и на другое нечетное количество пять элементов, больших в последней группе будет <tex>n</tex> <tex> mod</tex> <tex> 5)</tex> элементов. 2. Затем Выбираем медиану в каждой группе находим средний элемент (медиану), это можно сделать любой сортировкойиз этих групп. 3. И запускаем рекурсивно этот алгоритм от Путем рекурсивного вызова шага 1 определяется медиана <tex>x</tex> из множества медиан, найденных на втором шаге. Тем самым мы найдем средний <tex>x</tex> - рассекающий элемент среди медиан, то есть медиану медиан. Эту медиану медиан выберем рассекающим элементом для поиска <tex>ki</tex>-го индекс рассекающего элемента. Далее разбиваем  4.Делим массив на две части: слева от относительно рассекающего элемента числа <tex>x</tex>. Все элементы меньшие него<tex>x</tex> будут находиться левее <tex>x</tex> в массиве и будут иметь меньший индекс и наоборот, а справа - числа если элементы больше рассекающего элемента или равные ему<tex>x</tex>. 5.Если <tex>i</tex> <tex>=</tex> <tex>k</tex>, то возвращается значение <tex>x</tex>. И Иначе вызывается рекурсивно запускаем наш алгоритм от той шаг 1, и выполняется поиск <tex>k</tex>-го в порядке возрастания элемента в левой части массива, если <tex>i</tex> <tex><</tex> <tex>k</tex>, или в которой будет лежать правой части, если <tex>i</tex> <tex>></tex> <tex>k</tex>-й элемент.===Особенность алгоритма===