55
правок
Изменения
Нет описания правки
Этот алгоритм почти ни чем не отличается от алгоритма [[Поиск k-ой порядковой статистики|поиска k-ой порядковой статистики]], но имеет важное отличие в том, что время работы алгоритма в наихудшем случае равно <tex>O(n)</tex>, что будет доказано ниже. Главная идея алгоритма заключается в том, чтобы ''гарантировать'' хорошее разбиение массива. Алгоритм выбирает такой рассекающий элемент, что количество чисел, которые меньше рассекающего элемента, не менее <tex>\frac{3n}{10}</tex>, где <tex>n</tex> количество элементов в массиве, благодаря этому алгоритм работает за линейной время в любом случае.
== Описание алгоритма ==
#Все <tex>n</tex> элементов входного массива разбиваются на группы по пять элементов, в последней группе будет <tex>n</tex> <tex> mod</tex> <tex> 5</tex> элементов.Эта группа может оказаться пустой при <tex>n</tex> <tex>=</tex> кратных <tex>5</tex>.
#Сначала сортируется каждая группа, затем выбираем медиану в каждой из этих групп.
#Путем рекурсивного вызова шага 1 определяется медиана <tex>x</tex> из множества медиан, найденных на втором шаге. <tex>x</tex> — рассекающий элемент, <tex>i</tex> — индекс рассекающего элемента.Если медиан окажется четное количество, то на место рассекающего элемента будут претендовать две медианы, переменной <tex>x</tex> будет присвоено значение большей из этих двух медиан.
{
if (r - l + 1 <= 5) {
sort(A[l..r]); //если элементов не больше 5, сортируем их и возвращаем к-ый элемент
return A[k];
}
for i = l:5:..(r - 4)
sort(A[i..i + 4]; //сортируем каждую группу
i += 5; len n = r - l + 1; Medians[1..n/5] = A[(l + 2):5:(r - 2)]; //создаем массив медиан j = l + 2; for i = 1..n / 5 Medians[i] = A[j] j += 5;
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);
