2.2.4.3 — тот же компромисс, что у IntroSort (2.2.1.7), но для выбора k-го элемента2.2.4.3 — the same trade-off as IntroSort (2.2.1.7), but for selecting the k-th element
Quickselect (2.2.4.1) быстр почти всегда, но теоретически уязвим к Θ(n²). Медиана медиан (2.2.4.2) гарантирует O(n) всегда, но с большой константой, из-за которой почти всегда работает медленнее quickselect на обычных данных. Introselect — тот же принцип, что у IntroSort: начать с быстрого quickselect, следить за глубиной рекурсии, и если она превышает разумный предел (признак того, что pivot'ы систематически неудачны), переключиться на гарантированную медиану медиан.Quickselect (2.2.4.1) is fast almost always, but theoretically vulnerable to Θ(n²). Median of medians (2.2.4.2) guarantees O(n) always, but with a large constant that makes it almost always slower than quickselect on ordinary data. Introselect follows the same principle as IntroSort: start with fast quickselect, track recursion depth, and if it exceeds a reasonable limit (a sign that pivots are systematically unlucky), switch to the guaranteed median of medians.
Как и в IntroSort (2.2.1.7), заранее вычисляется лимит глубины depth_limit = 2·log₂(n) — величина, которую честный (в среднем сбалансированный) quickselect не должен превышать почти никогда. Алгоритм работает как обычный quickselect (случайный pivot, partition, рекурсия в одну сторону), пока глубина рекурсии не превысит depth_limit. Как только это происходит — это сигнал, что серия pivot'ов оказалась систематически неудачной (аналог обнаружения "плохого" случая в IntroSort), и на следующем шаге вместо случайного pivot используется детерминированный, полученный методом медианы медиан, — восстанавливая гарантию быстрого сокращения диапазона на этом конкретном шаге. После одного такого "спасительного" шага можно вернуться к случайному pivot или продолжать использовать медиану медиан до конца — конкретные реализации отличаются в деталях, но общий принцип — двухуровневая защита — одинаков.Just like IntroSort (2.2.1.7), a depth limit depth_limit = 2·log₂(n) is precomputed — a value honest (on-average-balanced) quickselect should almost never exceed. The algorithm runs as ordinary quickselect (random pivot, partition, single-direction recursion) as long as recursion depth doesn't exceed depth_limit. Once it does — that's a signal the sequence of pivots has been systematically unlucky (the selection analogue of detecting a "bad" case in IntroSort) — and on the next step a deterministic pivot obtained via median of medians is used instead of a random one, restoring the guarantee of a fast range reduction at that specific step. After one such "rescue" step, implementations may revert to a random pivot or keep using median of medians to the end — details vary, but the overall two-tier defense principle is the same.
"обычный путь" почти бесплатен, "запасной путь" гарантирует, что застревание невозможноthe "normal path" is nearly free, the "fallback path" guarantees getting stuck is impossible
int introselect(std::vector<int>& a, int k) {
int n = (int)a.size();
int depth_limit = int(2 * std::log2(std::max(n, 2)));
int lo = 0, hi = n - 1;
while (true) {
if (lo == hi) return a[lo];
int pivot_val;
if (depth_limit > 0) {
pivot_val = a[lo + rand() % (hi - lo + 1)]; // быстрый путь// fast path
} else {
pivot_val = median_of_medians(a, lo, hi); // гарантированный путь (2.2.4.2)// guaranteed path (2.2.4.2)
}
int p = partition_around(a, lo, hi, pivot_val);
if (k == p) return a[k];
else if (k < p) hi = p - 1;
else lo = p + 1;
--depth_limit;
}
}Кнопка "Худший случай" строит вход, специально устроенный так, чтобы каждый случайный выбор pivot (в этой демонстрации — фиксированно первый элемент, чтобы гарантированно показать переключение) оказывался неудачным. Наблюдайте, как счётчик глубины достигает лимита и алгоритм переключается на медиану медиан (синяя рамка вместо жёлтой).The "Worst case" button builds an input specifically constructed so every pivot choice (in this demo, fixed to the first element, to reliably trigger the switch) turns out unlucky. Watch the depth counter reach the limit and the algorithm switch to median of medians (blue outline instead of yellow).
нажмите «Вперёд» или «Играть», чтобы начатьpress "Forward" or "Play" to begin
Можно было бы отслеживать напрямую "насколько несбалансированным оказался последний partition" и переключаться при обнаружении сильного перекоса — но глубина рекурсии как метрика проще и надёжнее: у честного quickselect с рандомизированным pivot глубина рекурсии до нахождения ответа ограничена O(log n) с высокой вероятностью (это доказуемый факт о случайном процессе разбиения), а превышение этой границы уже само по себе статистически значимый сигнал накопленного невезения, безотносительно того, был ли какой-то один конкретный partition особенно плохим. Тот же выбор метрики, что и в IntroSort (2.2.1.7) — не совпадение, а прямое следствие общности задачи partition-и-рекурсия.One could directly track "how unbalanced was the last partition" and switch upon detecting a strong skew — but recursion depth as a metric is simpler and more reliable: for honest quickselect with a randomized pivot, recursion depth before finding the answer is bounded by O(log n) with high probability (a provable fact about the random partitioning process), and exceeding that bound is itself a statistically significant signal of accumulated bad luck, regardless of whether any single specific partition was especially bad. The same metric choice as in IntroSort (2.2.1.7) — not a coincidence, but a direct consequence of the shared partition-and-recurse structure.
Стандартная функция выбора k-го элемента в C++ реализована именно как introselect — точно тот же выбор, что std::sort сделал в пользу IntroSort (2.2.1.7): быстро на практике, гарантированно не хуже O(n) в теории.C++'s standard k-th-element selection function is implemented precisely as introselect — the exact same choice std::sort made in favor of IntroSort (2.2.1.7): fast in practice, provably no worse than O(n) in theory.
Introselect — частный случай более общего инженерного паттерна: оптимистичный быстрый алгоритм с детектором деградации и переключением на медленный, но надёжный запасной вариант — тот же паттерн встречается, например, в адаптивных JIT-компиляторах (интерпретация → компиляция при "разогреве") и в сетевых протоколах (быстрый путь vs. путь восстановления после потери пакетов).Introselect is a special case of a more general engineering pattern: an optimistic fast algorithm with a degradation detector and a switch to a slower but reliable fallback — the same pattern shows up, for instance, in adaptive JIT compilers (interpretation → compilation on "warm-up") and network protocols (fast path vs. packet-loss recovery path).