Изменения
Нет описания правки
===Особенность алгоритма===
Как будет доказано ниже, время работы алгоритма в наихудшем случае равно <tex>O(n)</tex>. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива, так как чисел, которые меньше рассекающего элемента не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве.
===Псевдокод===
select(L,k)
{
if (length(L) <= 10)
{
sort L
return the element in the kth position //вернем элемент, находящийся на k-ой позиции;
}
partition L into subsets S[i] of five elements each //разобьем L на подмножества S[i] размером 5 по 5 элементов;
(there will be n/5 subsets total).
for (i = 1 to n/5) do
x[i] = select(S[i],3) //найдем медианы S[i];
M = select({x[i]}, n/10) // M - рассекающий элемент;
partition L into L1<M, L2=M, L3>M
// разобьем L на подмножества L1, где все элементы меньше M, L3, где все элементы больше M и L2 равное M;
if (k <= length(L1))
return select(L1,k)
else if (k > length(L1)+length(L2))
return select(L3,k-length(L1)-length(L2))
else return M // элемент на k-ой позиции в исходном массиве;
}
===Пример===
На вход подается массив, разобьем элементы на группы по 5 элементов.
