Условие:
Время выполнения быстрой сортировки (Quicksort) зависит от того, насколько сбалансированными получаются разбиения. Если в качестве опорного элемента (pivot) выбирать наименьший или наибольший элемент, то массив будет делиться крайне неравномерно — по одному элементу за раз, и время выполнения приблизится к квадратичному, как у сортировки вставками (Insertion Sort).
Однако на практике Quicksort обычно работает значительно быстрее. Цель этого задания — сравнить скорость работы двух алгоритмов: количество обменов (swaps) в Quicksort (реализованном определённым образом) и количество сдвигов (shifts) в Insertion Sort — и вычислить их разность.
Требования к реализации Quicksort:
Используйте Lomuto partition scheme.
В качестве опорного элемента всегда берите последний элемент текущего подмассива.
\nQuicksort должен сортировать массив на месте (in-place).
Подсчёт обменов:
Любая операция, когда элемент меняется местами с другим (даже если позиция не меняется), считается за один swap.
В частности, нужно считать:
Обмен, когда элемент оказывается меньше опорного и перемещается в левую часть.
Финальный обмен, когда опорный элемент ставится на своё место (между левой и правой частями).
Подсчёт сдвигов для Insertion Sort:
Используйте стандартный подсчёт из предыдущих задач: количество сдвигов (shifts), т.е. сколько раз элемент перемещается влево через уже отсортированную часть массива.
Формат ввода:
Первая строка: целое число n — размер массива.
Вторая строка: n целых чисел — элементы массива.
Формат вывода:
Одно целое число D, вычисляемое по формуле:\nD=(количество сдвигов в Insertion Sort)−(количество обменов в Quicksort)
Ограничения:
1≤n≤1000
−1000≤x≤1000,x∈ar
