Изменения
Нет описания правки
<wikitex>
Partition(A, p, r)
x = A[pq]
i = p - 1
j = r + 1
while true
do repeat j = j - 1
until A[j] \le leq x
repeat i = i + 1
until A[i] > x
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
<tex>T(n) = \max(T(q)+T(n-q-1))+\Theta(n)</tex>,где <tex>0 \leq q \leq n-1</tex>,
так как мы разбиваемся на 2 подзадачи.
{{
Лемма
|statement=Пусть Х {{- --}} полное количество сравнений элементов с опорным за время работы сортировки. Тогда время работы сортировки равно <tex>O(n \log n)</tex>.
|proof=Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1...z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
