Не могу понять алгоритм быстрого выбора

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

int a[4] = {1,3,5,2} ;

Теперь предположим, что мы выбираем опорную точку случайным образом, тогда в соответствии с этим сообщением у нас есть следующие условия:

  • k == pivot. Тогда вы уже нашли k-е наименьшее. Это потому, что раздел работает. Ровно k - 1 элементов меньше, чем k-й элемент.

  • k < pivot. Тогда k-й наименьший находится слева от оси поворота.

  • k > pivot. Тогда k-й наименьший находится справа от оси поворота. И чтобы его найти, вам нужно найти справа наименьшее число k-pivot.

Я был бы признателен, если бы кто-нибудь мог объяснить, как k==pivot означает, что мы нашли k-й (в моем случае 2-й наименьший элемент). Также, если это k < pivot, повторить процесс для левой стороны поворота?


c++ algorithm data-structures quicksort quickselect
person Rajeshwar    schedule 16.03.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Да, когда pivok == k, у вас есть k-1 элементов слева от точки поворота, которые меньше, чем точка поворота, поэтому вы нашли k-th наименьшее число в массиве, т. Е. Точку поворота, но если k < pivot, выполните поиск слева сторона массива, потому что поворотный > k-й наименьший элемент, в противном случае поворот ‹ k-го наименьшего элемента массива, поэтому ищите справа, чтобы увеличить поворот.
from wikipedia:

// Returns the n-th smallest element of list within left..right inclusive (i.e. n is zero-based).
  function select(list, left, right, n)
     if left = right        // If the list contains only one element
         return list[left]  // Return that element
     pivotIndex  := ...     // select a pivotIndex between left and right, e.g. left + Math.floor(Math.random() * (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if n = pivotIndex
         return list[n]
     else if n < pivotIndex
         return select(list, left, pivotIndex - 1, n)
     else
         return select(list, pivotIndex + 1, right, n)

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

person Aseem Goyal    schedule 16.03.2014

arrow_upward
2
arrow_downward

Если k = pivot, у вас будет k-1 элементов слева от pivot. Благодаря разделению каждый из них меньше, чем основной элемент. Кроме того, благодаря разделению каждый из элементов справа больше, чем элемент сводной таблицы. Следовательно, опорный элемент должен быть k-м по величине. Имеет смысл?

person Joni    schedule 16.03.2014