Quickselect: разбить и спуститься в одну сторону

Если ты умеешь написать quickselect (разбить, сравнить k с позицией опорного, спуститься в одну сторону) и объяснить, почему в среднем это Θ(n) через сумму n + n/2 + n/4 + …, листай до «Теперь сам».

Как думаешь, что если сортировать только нужную половину

Быстрая сортировка разбивает массив опорным и рекурсивно сортирует ОБЕ половины. Но нам для задачи выбора порядок обеих половин не нужен - нужен один элемент ранга k. После разбиения опорный стоит на своей финальной позиции p: слева от него всё меньше, справа всё больше. И тут видно главное: если наш k меньше p - искомое ТОЧНО в левой части, правую можно вообще не трогать. Если больше - наоборот. Зачем сортировать половину, в которой ответа заведомо нет? Выбросим её целиком и продолжим только в нужной. Быстрая сортировка ветвится надвое, а выбор - спускается по одной ветке. Из этой экономии и рождается линия вместо n·log n.

На что это похоже

Толстый телефонный справочник и фамилия на букву «П». Ты не читаешь его подряд - открываешь примерно посередине, видишь букву «Л» и мгновенно ОТБРАСЫВАЕШЬ всю первую половину: «П» дальше. Открываешь середину оставшегося, видишь «Т» - отбрасываешь хвост. Ты каждый раз выкидываешь целый КУСОК, а не листаешь. Quickselect делает то же с массивом: разбиение говорит «твой элемент в этой половине», и вторую ты выбрасываешь не глядя. Разница с двоичным поиском лишь в том, что «середину» задаёт не индекс, а разбиение по опорному, - но идея «выбросить половину и продолжить в одной» та же.

Механизм: разбиение и спуск в одну часть

Возьмём разбиение Ломуто (проще для выбора): опорный - последний элемент, проходим массив, собирая слева все, кто меньше опорного, и в конце ставим опорный за ними - на позицию p.

выбор(a, lo, hi, k):        # ищем k-ю статистику среди a[lo..hi], k - глобальный индекс (с 0)
    если lo == hi:  вернуть a[lo]          # один элемент - он и есть ответ
    p = разбить(a, lo, hi)                 # опорный встал на p; слева < a[p], справа > a[p]
    если k == p:  вернуть a[p]             # опорный - ровно k-й, нашли
    если k <  p:  вернуть выбор(a, lo, p-1, k)   # ответ слева
    иначе:        вернуть выбор(a, p+1, hi, k)   # ответ справа

Ключевое - ОДНА из двух рекурсивных веток, а не обе. Позиция p после разбиения - это истинный ранг опорного: раз слева от него ровно p − lo элементов меньше, опорный стоит на своём месте навсегда. Сравнив k с p, мы точно знаем, в какой части искать, и вторую отбрасываем целиком.

Правило

Quickselect находит k-ю порядковую статистику за Θ(n) в среднем. Разбиваем массив опорным (опорный встаёт на свой истинный ранг p): если k == p - ответ найден; если k < p - рекурсия ТОЛЬКО в левую часть, если k > p - только в правую. В отличие от быстрой сортировки, спускаемся по ОДНОЙ ветке, отбрасывая вторую целиком. При сбалансированных разбиениях работа n + n/2 + n/4 + … = 2n = Θ(n). Та же операция разбиения, но одна рекурсия вместо двух - и n·log n превращается в n.

Разбор: почему в среднем Θ(n), а не Θ(n·log n)

Сравним рекуррентности выбора и сортировки - разница в одной ветке. Быстрая сортировка при хорошем разбиении: T(n) = 2·T(n/2) + Θ(n) - ДВЕ подзадачи, итог Θ(n·log n). Quickselect: T(n) = T(n/2) + Θ(n) - ОДНА подзадача (спускаемся в одну половину). Разверни сумму работы: разбить весь массив стоит ≈ n, потом половину - ≈ n/2, потом четверть - ≈ n/4, и так далее: n + n/2 + n/4 + … = n·(1 + 1/2 + 1/4 + …) = 2n. Геометрический ряд со знаменателем 1/2 сходится к удвоенному первому члену, поэтому сумма - Θ(n), а не Θ(n·log n). Именно исчезновение ВТОРОЙ ветки убирает множитель log n: у сортировки уровней log n и каждый стоит n (итог n·log n), у выбора работа на каждом уровне падает вдвое и вся сумма схлопывается в линию. (Строго это средний случай при случайных разбиениях; про худший - следующий урок.)

Разбор: почему это тот же разбиение, что в быстрой сортировке

Полезно увидеть, что мы не изобретаем новый алгоритм, а переиспользуем разбиение. Разбиение делает ровно одно: ставит опорный на его окончательное место p и раскладывает остальных на «меньше» слева и «больше» справа - за один линейный проход, Θ(n). Быстрая сортировка вызывает его и рекурсивно упорядочивает ОБЕ стороны (порядок нужен весь). Quickselect вызывает то же разбиение, но, зная свой k, спускается в ОДНУ сторону - порядок другой стороны ему не нужен, как мы обсуждали в прошлом уроке. Отсюда важное следствие: quickselect переставляет элементы массива (как и сортировка), то есть работает на месте, O(1) дополнительной памяти (не считая стека рекурсии, а его можно убрать циклом). И ещё: вызвав выбор, ты бесплатно получаешь РАЗБИЕНИЕ массива вокруг ответа - слева всё меньше k-й статистики, справа больше; это готовый «топ-k» без отдельной сортировки.

Что ломается без этого

Первая ошибка - спускаться в ОБЕ стороны (как в быстрой сортировке): получишь Θ(n·log n) и потеряешь весь смысл выбора. Идёшь строго в одну - ту, где по сравнению k с p лежит ответ. Вторая - перепутать, что сравнивать: k - это ГЛОБАЛЬНЫЙ индекс искомого (с 0), а p - позиция опорного в том же массиве; сравнивать надо именно их, а не k с длиной части. Третья - забыть базу lo == hi (один элемент - ответ) и уйти в бесконечную рекурсию. Четвёртая - неверно перевести «k-я статистика» (с 1) в индекс: ищем элемент с индексом k−1. Пятая - думать, что раз это Θ(n) в среднем, то и в худшем: нет, при плохих опорных выбор деградирует до Θ(n²) - об этом следующий урок.

Зачем это в работе

Quickselect - стандартный способ найти медиану, перцентиль или топ-k за линейное время в среднем, без полной сортировки. В Python это statistics и библиотеки численного анализа (numpy.partition - ровно разбиение вокруг k-го без сортировки), в C++ - std::nth_element. Мониторинг задержек считает 99-й перцентиль на миллионах измерений именно так - сортировать всё было бы дороже в log n раз. Топ-k результатов (лучшие 10 из миллиона) - это выбор (n−k)-й статистики как порога плюс отбор всех, кто выше; выбор дал заодно и разбиение вокруг порога. Важно помнить оговорку: Θ(n) тут - средний случай, и стандартные реализации подстраховывают его от худшего (следующие два урока) - но идея «разбей и спустись в одну сторону» лежит в основе их всех.

Теперь сам

В массиве после разбиения [2, 1, 4, | 5 |, 8, 9] опорный 5 встал на позицию p = 3 (индексация с 0). Ты ищешь k = 4-й по порядку элемент (индекс 4). Куда спускается quickselect и почему правую часть трогаем, а левую - нет?