55
правок
Изменения
Нет описания правки
#Если <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>.
===Псевдокод===
select(A, l, r, k){
if (r - l + 1 <= 5) {
j += 5;
x = select(Medians, 1, n/5, n/10); //x - рассекающий элемент
A = share(A, l, r, x); //делим массив относительно элемента x
