55
правок
Изменения
Нет описания правки
===Псевдокод===
select(A, l, r, k)
{ //если элементов не больше 5, сортируем их и возвращаем к-ый элемент
if (r - l + 1 <= 5) {
sort(A[l..r]); //если элементов не больше 5, сортируем их и возвращаем к-ый элемент
return A[k];
}
//сортируем каждую группу
for i = l..(r - 4)
sort(A[i..i + 4]; //сортируем каждую группу
i += 5;
//создаем массив медиан
n = r - l + 1;
j = l + 2; //создаем массив медиан
for i = 1..n / 5
Medians[i] = A[j]
j += 5;
//x - рассекающий элемент x = select(Medians, 1, n/5, n/10); //делим массив относительно элемента x - рассекающий элемент A = share(A, l, r, x); //делим массив относительно находим индекс элемента xв исходном массиве
for i = l to r
if (A[i] == x)
m = i; //находим индекс элемента x в исходном массиве
if (m = k)
return A[m];
//делаем рекурсивный вызов от той части массива, где находится к-ый элемент
if (m > k)
select(A, k, r, m - k + 1); //делаем рекурсивный вызов от той части массива, где находится к-ый элемент
else
select(A, l, k, m);
