Особенности работы быстрой сортировки

Время работы алгоритма быстрой сортировки зависит от того, как разбива­ется массив на каждом шаге. Если разбиение происходит на примерно равные части, время работы составляет O (n ×log n), как и для сортировки слиянием. Если же размеры частей сильно отличаются, сортировка может занимать время O (п²), как при сортировке вставками.

«Наиболее неравные части» получатся, если одна часть содержит n – 1 элемент, а вторая – всего 1. Предположим, что на каждом шаге происходит именно так. Поскольку процедура разбиения занимает время Q(n), для времени работы Т (п)получается соотношение

Поскольку T (1) = Q(l)

Т.е. время работы быстрой сортировки в худшем случае равно Q(n ²).

Рисунок 2.6 – Дерево рекурсии процедуры Quicksort для наихудшего случая

Рисунок 2.7 – Дерево рекурсии процедуры Quicksort для наилучшего случая

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