Понимание медианы алгоритма медиан

Проблема заключается в шаге, где вы говорите найти истинную медиану медиан. В вашем примере у вас были эти медианы:

50 45 40 35 30 25 20 15 10

Истинная медиана этого набора данных равна 30, а не 15. Вы не найдете эту медиану, разбивая группы на блоки по пять и взяв медиану этих медиан, а вместо этого рекурсивно вызывая алгоритм выбора для этой меньшей группы. Ошибка в вашей логике предполагает, что медиана этой группы находится путем разделения приведенной выше последовательности на два блока.

50 45 40 35 30

и

25 20 15 10

затем найти медиану каждого блока. Вместо этого алгоритм медианы медиан будет рекурсивно вызывать себя на полном наборе данных 50 45 40 35 30 25 20 15 10. Внутренне это разделит группу на блоки из пяти и отсортирует их и т. д., но это делается для определения точки разделения для шага разделения, и именно на этом шаге разделения рекурсивный вызов найдет истинную медиану медиан. , что в данном случае будет равно 30. Если вы используете 30 в качестве медианы в качестве шага разбиения в исходном алгоритме, вы действительно получите очень хорошее разделение, как и требовалось.

Надеюсь это поможет!

Вот псевдокод для медианного алгоритма медиан (слегка измененный для вашего примера). Псевдокод в википедии не отражает внутреннюю работу вызова функции 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)

1. При первом вызове M = select({x[i]}, n/10) массив {x[i]} будет содержать следующие числа: 50 45 40 35 30 20 15 10. В этом вызове n = 45, и, следовательно, вызов функции select будет M = select({50 45 40 35 30 20 15 10}, 4)

2. При втором вызове 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 или меньше элементов, следовательно, он вернет элемент в k-й, т.е. 1-й позиции в отсортированном массиве, что равно 30).

Теперь M = 30 будет получено при первом вызове функции select по всему массиву из 45 элементов, и та же логика разбиения, которая разделяет массив L вокруг M = 30, будет применена для окончательного получения медианы медиан.

Фу! Надеюсь, я был достаточно подробным и ясным, чтобы объяснить алгоритм медианы медианы.