Quickselect

Поддерживается диапазон [lo, hi], про который известно: искомый k-й (по глобальному индексу) элемент лежит внутри него. На каждом шаге выполняется тот же partition, что и в quicksort — выбирается pivot, массив переставляется так, что все элементы меньше pivot оказываются слева от него, все большие — справа, и pivot встаёт на свою финальную позицию p. Дальше сравнивается p с k: если p == k, pivot и есть искомый элемент — поиск завершён; если k < p, ответ гарантированно слева, и рекурсия (или следующая итерация цикла) идёт только в [lo, p-1]; если k > p, ответ справа, [p+1, hi]. Вторая половина не трогается вообще — ни рекурсии, ни какой-либо дальнейшей обработки над ней не происходит.A range [lo, hi] is maintained, about which it's known: the (globally indexed) k-th element lies inside it. Each step runs the same partition as quicksort — a pivot is chosen, the array is rearranged so every element less than the pivot ends up to its left and every larger one to its right, and the pivot lands at its final position p. Then p is compared to k: if p == k, the pivot is the answer — search over; if k < p, the answer is guaranteed to be on the left, and recursion (or the next loop iteration) goes only into [lo, p-1]; if k > p, the answer is on the right, [p+1, hi]. The other half isn't touched at all — no recursion, no further processing of any kind happens on it.

int quickselect(std::vector<int>& a, int k) {
    int lo = 0, hi = (int)a.size() - 1;
    while (true) {
        if (lo == hi) return a[lo];
        int pivot_idx = lo + rand() % (hi - lo + 1);  // случайный pivot против adversarial входа// random pivot against adversarial input
        int p = partition(a, lo, hi, pivot_idx);       // тот же partition, что в quicksort// the same partition as quicksort
        if (k == p) return a[k];
        else if (k < p) hi = p - 1;  // ответ слева — правая часть больше не нужна// answer is on the left — the right side is no longer needed
        else lo = p + 1;             // ответ справа — левая часть больше не нужна// answer is on the right — the left side is no longer needed
    }
}

Оранжевая рамка — текущий рабочий диапазон [lo, hi]. Затемнённая часть — уже отброшенная сторона, которая больше никогда не будет прочитана. Жёлтый столбик — pivot после partition; зелёный — найденный k-й элемент.The orange outline is the current working range [lo, hi]. The dimmed part is the already-discarded side, never read again. The yellow bar is the pivot after partitioning; green is the found k-th element.

В quicksort суммарная стоимость всех partition на одном "уровне" рекурсии — O(n), а уровней в среднем O(log n), что даёт O(n log n). В quickselect работа выполняется только над одной убывающей веткой: partition на диапазоне размера n стоит O(n), но следующий диапазон в среднем сжимается в константу раз (например, вдвое при удачном pivot), поэтому суммарная стоимость — геометрическая прогрессия n + n/2 + n/4 + ... = O(n) (сумма сходится к 2n). Именно отбрасывание "лишней" рекурсии, а не более быстрый partition, даёт переход от O(n log n) к O(n).In quicksort, the total cost of all partitions at one recursion "level" is O(n), and there are O(log n) levels on average, giving O(n log n). In quickselect, work happens only along one shrinking branch: partitioning a range of size n costs O(n), but the next range on average shrinks by a constant factor (e.g. halves with a lucky pivot), so the total cost is the geometric series n + n/2 + n/4 + ... = O(n) (the sum converges to 2n). It's discarding the "extra" recursion, not a faster partition, that produces the drop from O(n log n) to O(n).

Худший случай остаётся Θ(n²) по той же причине, что у quicksort: неудачный (например, детерминированный) выбор pivot на adversarial входе может каждый раз отсекать только один элемент, оставляя диапазон размера n-1, n-2, ... — сумма n + (n-1) + (n-2) + ... = Θ(n²). Решение той же природы, что и в 2.2.1.4 — случайный выбор pivot делает такой сценарий статистически невозможным, но не устраняет его как теоретическую возможность; полное устранение худшего случая — тема следующей статьи, медианы медиан (2.2.4.2).The worst case remains Θ(n²) for the same reason as quicksort: an unlucky (e.g. deterministic) pivot choice on adversarial input can cut off just one element each time, leaving ranges of size n-1, n-2, ... — the sum n + (n-1) + (n-2) + ... = Θ(n²). The fix is the same as in 2.2.1.4 — random pivot selection makes this scenario statistically impossible, but doesn't eliminate it as a theoretical possibility; fully eliminating the worst case is the topic of the next article, median of medians (2.2.4.2).