Информатика · объяснение и практика

Порядковая статистика: найти k-й элемент без полной сортировки

Поиск k-го наименьшего элемента: локальный ранг после разбиения, повторяющиеся значения и выбор только нужной области.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

В маршруте Сортировки и сравнение строк · 10 тем

Главная мысль

Чтобы найти k-й элемент по возрастанию, не обязательно полностью сортировать список. После разбиения вокруг опоры можно определить, в какой области находится нужный ранг, и продолжить только там. Здесь ранги считаются с единицы и учитывают все повторения.

Уточняем, что означает нужное место

Для списка 6, 2, 6, 1 четвёртый по возрастанию элемент равен шести, а третий тоже равен шести. Повторяющиеся значения занимают отдельные места. Если же нужен третий различный результат, это другая задача: сначала требуется определить работу с уникальными значениями.

В учебном варианте разбиение создаёт три части: меньше опоры, равно ей и больше. Пусть в первой части L элементов, во второй E элементов. Тогда ранги от одного до L относятся к меньшей части, следующие E рангов — к равной, а остальные — к большей. Внутри каждой части полная сортировка пока не нужна.

Пересчитываем ранг в выбранном остатке

Возьмём список 8, 3, 6, 3, 10, 1, 7 и опору шесть. Меньшая часть содержит 3,3,1: её длина три. Равная часть содержит одну шестёрку. Большая — 8,10,7. Значит, четвёртый элемент сразу найден: это опора.

Если требуется шестой элемент, он находится в большей части. Внутри неё его локальный ранг равен 6−3−1=2. Теперь задача состоит в поиске второго наименьшего среди 8,10,7. Если забыть вычесть уже пропущенные области, получится другой запрос и, возможно, выход за допустимые границы.

Пример

Для [8,3,6,3,10,1,7] шестой элемент: выбираем [8,10,7] с локальным рангом 2. Результат 8.

Полная проверочная сортировка даёт [1,3,3,6,7,8,10]. Число 8 действительно стоит на шестом месте.

Как проверять ответ и оценивать работу

Найденное значение удобно проверять двумя подсчётами: сколько исходных элементов строго меньше него и сколько не больше. Для k-го элемента должно выполняться: строго меньших меньше k, а не больших — хотя бы k. Эти условия корректно учитывают повторения, когда несколько рангов дают одинаковый ответ.

Выбор опоры влияет на объём дальнейшей работы. Удачные разбиения быстро уменьшают оставшуюся область, неудачные могут оставлять почти весь список. Поэтому обычный quickselect не обещает линейное время на любом конкретном входе. Главное отличие от быстрой сортировки здесь — после разбиения рассматривают только нужную сторону, а не обе.

От чтения к действию

А теперь — вы

В меньшей части 4 элемента, в равной 2. Ищем 8-й по возрастанию. Какой локальный ранг нужен в большей части?

Частые вопросы

Третий элемент и третье различное число — одно и то же?

Нет. В этой задаче повторения учитываются как отдельные места.

Почему в большей части уменьшается k?

Перед ней уже находятся L меньших и E равных опоре элементов; эти места нужно вычесть из исходного ранга.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться