Изменения
→Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента
</center>
Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное максимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента).
Таким образом, так как каждый раз массив разбивается на две части {{---}} большие или равные опорному элементы и меньшие его {{---}} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений.
Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex> если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex> и <tex>X_{ij} = 0</tex>, если сравнения не произошло.
Применим к обоим обеим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим
<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>
s.push(l, i - 1)
В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex> n 1</tex> — вся обработка пройдёт в цикле первого уровня рекурсии.
===Улучшенная быстрая сортировка===
