Раздел в 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--; 
    } 

} 

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

Неправильно ли этот алгоритм?

Благодарим за помощь!

Answer 1

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

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

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

сделать комментарий, если вы сделали что-нибудь

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