У Никиты есть некоторое количество банок газировки разного объема. Он хочет найти k-ую по полезности банку, при этом

Поиск k-ой по полезности банки

Инструкция:
Для решения данной задачи мы можем использовать подход, основанный на сортировке. Однако, по условию требуется найти решение без использования встроенных алгоритмов сортировки.

Мы можем решить эту задачу, используя алгоритм частичной сортировки, называемый "QuickSelect". Этот алгоритм основан на разделении массива на две части, где одна часть содержит все элементы меньше выбранного элемента, а другая часть содержит все элементы больше выбранного.

Для решения задачи мы можем выбрать первый элемент как опорный, а затем разделить массив на две части, перемещая все элементы меньше опорного элемента влево, а все элементы больше опорного элемента - вправо. Если позиция опорного элемента равна k-1, то мы нашли искомое значение объема. В противном случае, мы можем рекурсивно применить этот процесс к части массива, где находится искомый элемент.

Демонстрация:
Входные данные: 5 5 1 7 2 3
1. В данном примере у нас есть 5 банок газировки с объемами 5, 1, 7, 2 и 3.
2. Мы хотим найти 5-ую по полезности банку.
3. Используя алгоритм QuickSelect, мы разделяем массив на две части: {1, 2, 3} и {7}.
4. Так как позиция опорного элемента (7) равна 4-ой позиции (индексация начинается с 0), мы нашли 4-ую по полезности банку.
5. Вывод: 7

Совет: При решении данной задачи стоит внимательно ознакомиться с алгоритмом QuickSelect и его особенностями. Также полезно разобраться в принципах работы алгоритмов сортировки, чтобы иметь представление о том, как происходит частичная сортировка.

Дополнительное задание:
Для практики решите задачу с другими входными данными:
Ввод: 7 3 10 4 8 2 5 6 7
Вывод: ? (найти объем 3-ей по полезности банки)