Изменения

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