Алгоритм Quickselect для поиска k-го по величине элемента в массиве работает следующим образом: 1

1. Выбор опорного элемента (pivot). 1 Обычно выбирается случайный элемент массива. 1
2. Разделение массива. 1 Массив делится на три части: элементы меньше опорного, элементы, равные опорному, и элементы больше опорного. 1
3. Рекурсия. 1 В зависимости от позиции k относительно размеров подмассивов, рекурсивно применяется Quickselect к нужной части. 1

Логика работы:

• Если индекс разделённого элемента (опорного) больше k, то рекурсируется левая часть. 45
• Если индекс равен k, то находится k-й по величине элемент и он возвращается. 45
• Если индекс меньше k, то рекурсируется правая часть. 45

В среднем случае временная сложность алгоритма составляет O(n), хотя в худшем случае может достигать O(n^2). 1