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

Question

В настоящее время я изучаю алгоритмы в свободное время, но у меня возникает следующий вопрос при изучении алгоритмов select () в главе 3.

Я понимаю, что могу использовать алгоритм select (), чтобы найти среднее число (n / 2-е наименьшее число), если бы я использовал массив от A до n чисел.

1), но это бит, который я изо всех сил пытаюсь понять.A = [3, 7, 5, 1, 4, 2, 6, 2].Предположим, что это массив.что такое содержимое массива после каждого вызова Partition () и параметры в каждом рекурсивном вызове Select ().

Может кто-нибудь объяснить, как они это решают, пожалуйста?

ниже приведен псевдокод для двух алгоритмов.

Select(A, p, r, k) {
    /* return k-th smallest number in A[p..r] */
    if (p==r) return A[p] /* base case */
    q := Partition(A,p,r)
    len := q – p + 1
    if (k == len) return A[q]
    else if (k<len) return Select(A,p,q-1,k)
    else return Select(A,q+1,r,k-len)
}

, а второй код -

Partition(A, p, r) { /* partition A[p..r] */
    x := A[r] /* pivot */
    i := p-1
    for j := p to r-1 {
        if (A[j] <= x) {
            i++
            swap(A[i], A[j])
        }
    }
    swap(A[i+1], A[r])
    return i+1
}

Книга, которую я использую, называется Вывод алгоритмов Энн Калдевай.

Answer 1

Этот алгоритм работает в два этапа. Шаг разделения работает, выбирая некоторый элемент поворота, затем переставляя элементы массива таким образом, чтобы все, что меньше, чем ось, было с одной стороны, все, что больше, чем опора, было с другой стороны, и опора находилась в правильном месте. Например, учитывая массив

3  2  5  1  4

Если мы выберем точку 3, то мы можем разделить массив следующим образом:

2  1  3  5  4
+--+  ^  +--+
 ^    |    ^
 |    |    +--- Elements greater than 3
 |    +-------- 3, in the right place
 +------------- Elements less than 3

Обратите внимание, что мы не отсортировали массив; мы только что сделали это ближе к сортировке. Это, кстати, первый шаг в быстрой сортировке.

Затем алгоритм использует следующую логику. Предположим, что мы хотим найти элемент, который принадлежит по индексу k в отсортированном порядке (k-й наименьший элемент). Затем, относительно выбранной нами оси, есть три варианта:

1. Поворот находится в положении k. Затем, так как пивот находится в правильном месте, значение, которое мы ищем, должно быть пивотом. Мы сделали.
2. Шарнир находится в положении больше, чем k. Тогда k-й наименьший элемент должен находиться в той части массива до точки поворота, чтобы мы могли рекурсивно искать в этой части массива k-й наименьший элемент.
3. Шарнир находится в положении меньше k. Тогда k-й наименьший элемент должен находиться где-то в верхней области массива, и мы можем вернуться туда.

В нашем случае предположим, что нам нужен второй по наименьшему элемент (тот, что в позиции 2). Поскольку ось оказалась в позиции 3, это означает, что второй по наименьшему элемент должен быть где-то в первой половине массива, поэтому мы бы вернулись на подмассив

2  1

Если бы мы хотели фактический медианный элемент, так как пивот оказался в центре массива, мы бы просто вывели, что медиана равна 3, и все будет готово.

Наконец, если бы мы хотели что-то вроде четвертого наименьшего элемента, то, поскольку пивот находится перед позицией 4, мы бы вернулись в верхнюю половину массива, а именно

5  4

и будет искать первый наименьший элемент здесь, так как перед этим регионом есть три элемента.

Остальная часть алгоритма - это детали того, как сделать шаг разбиения (что, вероятно, является наиболее сложной частью алгоритма) и как сделать трехсторонний выбор о том, рекурсировать или нет (немного менее сложно. ). Надеемся, однако, что эта структура высокого уровня помогает алгоритму иметь больше смысла.

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