76
правок
Изменения
→Алгоритм
end ;
unti l i > j ;
if l e f t left < j then QSort ( l e f t left , j ) ; if i < r i g h t right then QSort ( i , r i g h t right ) ;
end ;
begin
===Оптимизация глубины рекурсии до O(logn) в худшем случае===
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex>. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.
==Асимптотика==
Oh, boy, here we go!
