Иногда нужен только k-й наименьший элемент (индексы с 0): минимум, медиана, 90-й перцентиль. Сортировать весь массив за O(n log n) избыточно. Quickselect использует тот же partition, что и быстрая сортировка, но после каждого разбиения продолжает только с одной стороны и находит ответ в среднем за O(n). Это идея «разделяй и властвуй», см. разделяй и властвуй.

Разбиение вокруг опорного и выбор одной стороны
Разбиение вокруг опорного и выбор одной стороны

Разбиение Ломуто

Опорный — последний элемент. Цикл переносит элементы меньше опорного в начало, i — граница этой зоны. В конце опорный меняется местами с a[i]: это его итоговое место в отсортированном массиве.

python
def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

a = [7, 2, 9, 4, 3, 8, 5]
p = partition(a, 0, len(a) - 1)
print(a)
print("pivot index:", p)
text
[2, 4, 3, 5, 9, 8, 7]
pivot index: 3

Quickselect