Незаметный выбор места сортировки

Question

Вам дан массив A [1..n] длины n, в каждой ячейке которого содержится пара «рост, вес». Все значения роста различны, как и значения веса. Массив отсортирован в порядке возрастания значений высоты. Ваша задача - разработать рекурсивный алгоритм «разделяй и властвуй», который с целым числом k∈ [1, n] находит запись с k-м наименьшим значением веса. Вам разрешено использовать только O (1) дополнительного пространства на каждом уровне рекурсии. Хотя вашему алгоритму разрешено изменять порядок записей A, если это необходимо, он должен восстановить первоначальный порядок записей до завершения. Ваш алгоритм должен работать за Θ (n) времени.

Алгоритм, о котором я могу думать, это сортировка выбора, но я не могу сделать это в запрошенной сложности времени и пространства. Буду признателен за любую помощь или направление.

Answer 1

Если алгоритм может быть в среднем O (n), вы можете использовать быструю сортировку. Быстрая сортировка может найти k-й элемент в среднем за O (n), если используется до тех пор, пока не будет доказано, что ось является самим k-м элементом (O (n ^ 2) наихудший случай и O (n) в среднем).

Теперь сложная часть: вам нужно восстановить исходный массив. Это просто для первой итерации процедуры разбиения в отсортированном массиве: просто запустите процедуру в обратном направлении и восстановите исходный массив. Теперь возникает рекурсивная идея: если стержень оказывается больше, чем k-й элемент, вы все равно оставили отсортированный подмассив: вы можете повторить процедуру, найти k-й и восстановить массив. Но если вы обнаружите, что ось ниже k-го элемента ... тогда восстановите массив и запустите быструю сортировку "отраженной" (с которой вы начинаете двигаться справа налево). В этом случае правый подмассив из оси будет отсортирован. Повторите процедуру рекурсивно.