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

Question

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

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

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

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

k == pivot, Тогда вы уже нашли kth наименьшее. Это потому, что работает раздел. Есть ровно k — 1 элементов, которые меньше k-го элемента.
k < pivot, Тогда kth самый маленький находится на левой стороне оси.
k > pivot, Тогда kth самый маленький находится на правой стороне оси. И чтобы найти его, вам нужно найти наименьшее число k-pivot справа.

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

0

algorithm c++data-structures quickselect quicksort

Решение

Другие решения

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

2

Источник

Accepted Answer

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

// 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)

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

1