Изменения

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