Раздел в Quickselect

Question

Я должен реализовать алгоритм, который возвращает медиану массива. Поэтому я решил внедрить Quickselect, который, по-видимому, эффективен для этого, и увидел, что для трехчастного разбиения я могу использовать тот же алгоритм разбиения, что и в Quicksort.

Алгоритм разбиения, описанный в моих заметках к лекциям (в коде C), следующий:

for (i = lo, j = hi;
     (i <= j);)
{
    while (a[i] < pivot)
    {
        i++;
    }

    while (a[j] > pivot)
    {
        j--;
    }

    if (i <= j)
    {
        if (i < j)
        {
            /* exchange values */
            tmp = a[i];  
            a[i] = a[j];
            a[j] = tmp;
        }

        i++;
        j--;
    }

}

Теперь, если мой массив: a = [40, 20, 100, 60, 80], и я выбираю в качестве пивота число 80, результат будет: a = [40, 20, 80, 60, 100], но, как вы можно увидеть значения в правом разделе не все> 80 (у нас 60). Если я выберу любое другое число, алгоритм будет работать правильно.

Этот алгоритм неверен?

Заранее спасибо за помощь!

Answer 1

Для быстрого выбора вам нужно использовать рекурсивный алгоритм, который найдет правильную позицию элемента pivot, таким образом, разделив весь массив на 2halves [элементы справа от позиции pivot имеют значение меньше, чем pivot, а элементы слева от поворотная позиция имеет значение больше, чем поворотная точка]

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

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

прокомментируйте, если вы что-то поняли

Answer 2

[40, 20, 100, 60, 80]
          i ... #while (a[i] < pivot)

[40, 20, 100, 60, 80]
          i        j ... #while (a[j] > pivot)

[40, 20, 80, 60, 100]
          i        j ... #/* exchange values */

[40, 20, 80, 60, 100]
             ij ... #i++;j--;

[40, 20, 80, 60, 100]
              j   i  ... #while (a[i] < pivot)

[40, 20, 80, 60, 100] ... exit for-loop .. finish