2.1.12 Быстрая сортировка

Дан массив из n целых чисел. Отсортируйте его по неубыванию алгоритмом быстрой сортировки (Quick Sort). Выберите опорное значение, разделите обрабатываемую часть массива относительно него и отсортируйте полученные части тем же алгоритмом. Части, содержащие менее двух элементов, не требуют дальнейшей обработки.

Реализуйте алгоритм в отдельной функции void quick_sort(int array[], int left, int right), где left и right — включительные границы обрабатываемой части массива, индексация начинается с нуля. Функция должна изменять переданный массив и не выполнять ввод или вывод. В функции main прочитайте массив, вызовите quick_sort(array, 0, n - 1) и выведите результат. Для обработки частей используйте рекурсивные вызовы: функция вызывает сама себя для меньших частей массива.

Использование готовых функций сортировки, включая qsort и std::sort, запрещено. Алгоритм должен корректно обрабатывать повторяющиеся значения, в том числе массив из одинаковых чисел. При разделении границы должны продвигаться даже при равенстве элементов опорному значению, а последующие вызовы должны получать меньшие части. Учитывайте, что выбор опорного значения влияет на скорость сортировки и глубину рекурсии; проверьте решение также на уже отсортированном массиве и массиве в обратном порядке.

Материал к заданию

Основные виды сортировок и примеры их реализации — Яндекс Образование, раздел «Быстрая сортировка». Реализацию из статьи адаптируйте к массиву и включительным границам left, right, заданным в условии. Выбор последнего элемента в качестве опорного, использованный в статье, может приводить к квадратичному числу операций и линейной глубине рекурсии на отсортированных массивах и массивах из одинаковых значений; при разработке учитывайте указанные в условии случаи.

Время: 2 секунды. Память: 64 МиБ. Вывод: до 2 МиБ. Стандарты: C11 / C++17.

В первой строке вводится целое число n — количество элементов массива. Во второй строке вводятся n целых чисел, разделённых пробелами. Ограничения: 1 ≤ n ≤ 10000, −10⁹ ≤ aᵢ ≤ 10⁹. Значения могут повторяться.

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