Предположим, дан массив чисел, который нужно отсортировать с помощью алгоритма быстрой сортировки. Но оказалось, массив уже отсортирован.
Допустим, вы взяли в качестве опорного самый первый элемент массива.
На первом шаге ведущий элемент 0. Чтобы получить три подмассива, нужно сравнить с опорным
(n−1) элемент.
На втором шаге примем за опорный элемент 3. Будет выполнено
(n−2) операции сравнения. На каждом шаге количество сравнений будет уменьшаться на 1. Когда останется 1 элемент в массиве, сравнивать его будет не с чем. Поэтому получится 0 операций сравнения.
Таким образом, чтобы посчитать общее количество сравнений, проделанных алгоритмом, нужно посчитать сумму:
(n−1)+(n−2)+(n−3)+...+1. Это сумма арифметической прогрессии. Её формула:
Если подставить в формулу получившиеся для алгоритма значения, получится
2n2−n=O(n2).Получили сортировку, которая асимптотически работает ничуть не быстрее сортировки пузырьком, вставками или выбором!
Не всё так плохо. Посчитаем сложность алгоритма на том же примере, если опорный элемент на каждом шаге выбран удачно и разделит массив пополам.
На каждом шаге проделаем
O(n) операций. Количество шагов деления (глубина рекурсии) составляет
logn. Если повезёт, и каждый раз будем выбирать центральный элемент, то основание логарифма будет 2.
Рассмотрим работу алгоритма на примере произвольного массива.
Также получим логарифмическое количество итераций. Общее быстродействие на практике:
O(nlogn).
Гоша: Как же выбрать опорный элемент?
Тимофей: Неплохой стратегией будет взять крайний левый элемент, крайний правый элемент, средний элемент и выбрать средний из них. Также хорошим вариантом является просто выбрать случайный элемент.