Изменения

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