Изменения
Нет описания правки
else return j
</wikitex>
==Асимптотика==
}}
Mатожидание времени работы быстрой сортировки будет <tex>O(n \log n)</tex>.
==Способы разбиения массива==
* При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(''n'' lg ''n'').
* Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов). Такой выбор также направлен против худшего случая.
* Разбивать массив не на две, а на три части
==Оптимизация глубины рекурсии до O(logn) в худшем случае==
Время работы алгоритма сортировки зависит от того, как разбивается массив на каждом шаге. В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex> а время работы алгоритма <tex>O(n^2)</tex>. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.
== Ссылки ==
