Вот псевдокод для алгоритма медианы медиан (немного изменен в соответствии с вашим примером). Псевдокод в википедии не отображает внутреннюю работу вызова функции selectIdx.
Я добавил комментарии к коду для объяснения.
// L is the array on which median of medians needs to be found.
// k is the expected median position. E.g. first select call might look like:
// select (array, N/2), where 'array' is an array of numbers of length N
select(L,k)
{
if (L has 5 or fewer elements) {
sort L
return the element in the kth position
}
partition L into subsets S[i] of five elements each
(there will be n/5 subsets total).
for (i = 1 to n/5) do
x[i] = select(S[i],3)
M = select({x[i]}, n/10)
// The code to follow ensures that even if M turns out to be the
// smallest/largest value in the array, we'll get the kth smallest
// element in the array
// Partition array into three groups based on their value as
// compared to median M
partition L into L1<M, L2=M, L3>M
// Compare the expected median position k with length of first array L1
// Run recursive select over the array L1 if k is less than length
// of array L1
if (k <= length(L1))
return select(L1,k)
// Check if k falls in L3 array. Recurse accordingly
else if (k > length(L1)+length(L2))
return select(L3,k-length(L1)-length(L2))
// Simply return M since k falls in L2
else return M
}
Если взять ваш пример:
Функция медианы медиан будет вызываться по всему массиву из 45 элементов, например (с k = 45/2 = 22):
median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2)
При первом вызове M = select({x[i]}, n/10) массив {x[i]} будет содержать следующие числа: 50 45 40 35 30 20 15 10.
В этом вызове n = 45, и, следовательно, вызов функции выбора будет M = select({50 45 40 35 30 20 15 10}, 4)
Во второй раз, когда вызывается M = select({x[i]}, n/10), массив {x[i]} будет содержать следующие числа: 40 20.
В этом вызове n = 9 и, следовательно, вызов будет M = select({40 20}, 0).
Этот вызов выбора вернется и присвоит значение M = 20.
Теперь, когда у вас возникли сомнения, мы теперь разбиваем массив L вокруг M = 20 на k = 4.
Запомните массив L здесь: 50 45 40 35 30 20 15 10.
Массив будет разбит на L1, L2 и L3 в соответствии с правилами L1 < M, L2 = M и L3 > M. Следовательно:
L1: 10 15
L2: 20
L3: 30 35 40 45 50
С k = 4 оно больше length(L1) + length(L2) = 3. Следовательно, поиск будет продолжен следующим рекурсивным вызовом:
return select(L3,k-length(L1)-length(L2))
что переводится как:
return select({30 35 40 45 50}, 1)
который вернет 30 в результате. (поскольку L имеет 5 или меньше элементов, следовательно, он вернет элемент в kth, то есть в 1-й позиции отсортированного массива, равной 30).
Теперь M = 30 будет получено при первом вызове функции select по всему массиву из 45 элементов, и та же логика разделения, которая разделяет массив L вокруг M = 30, будет применяться для окончательного получения медианы медиан.
Уф! Я надеюсь, что был достаточно многословен и ясен, чтобы объяснить алгоритм медианы медиан.