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

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

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

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

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

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

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

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