Разбиение массива будет произведено <tex>\Theta(n)</tex> раз, потому что разбиение производится на массивы длины <tex>1</tex> и <tex> n - 1 </tex> из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше). Следовательно, на массиве, который строится описанным выше способом, выполняется <tex>\Theta(n)</tex> <tex>\mathrm{partition}</tex> и <tex>\Theta(n)</tex> сравнений для каждого выполнения <tex>\mathrm{partition}</tex>. Тогда быстрая сортировка выполнит <tex>\Theta(n^2)</tex> сравнений для массива, построенного таким способом.
===Способ построить массив с максимальным количеством сравнений при выборе детерминированного элемента в качестве опорного=== Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае - <tex>\Theta(n^2)</tex>) количество сравнений. Такое число сравнений, очевидно, достигается при разбиении на массивы длиной <tex>1</tex> и <tex>n-1</tex> на каждой итерации. Создадим массив <tex>Arr</tex> длины <tex>n</tex>, заполненный элементами типа <tex>pair</tex>. Такой элемент хранит пару значений <tex>(val, key)</tex>, где <tex>val</tex> - элемент массива, а <tex>key</tex> - индекс. Изначально <tex>Arr(i)</tex> элемент имеет вид <tex>(0, i)</tex>. Далее, запустим для данного массива алгоритм быстрой сортировки. На каждом шаге будем выполнять следующие действия: при обращении к <tex>i</tex>-ому элементу в качестве опорного, присвоим для него <tex>val = n-i</tex>. После чего выполним шаг сортировки. После завершения работы алгоритма сортировки, искомым будет являться массив из <tex>val(i)</tex>, отсортированных по индексам <tex>key(i)</tex>. Пример для <tex>n = 4</tex>, при последовательном выборе опорных элементов <tex>2, 2, 1, 1</tex>. <center> {| class="wikitable"!colspan="8"| Построение массива |- ! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0 |-align="right"| 1 2 3 4 0 '''0''' 0 0 | 1 2 3 4 0 '''4''' 0 0| 1 3 4 2 0 0 0 '''4'''| 1 3 4 2 0 '''0''' 0 4| 1 3 4 2 0 '''3''' 0 4| 1 4 3 2 0 0 '''3''' 4| 1 4 3 2 '''0''' 0 3 4|-! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || Результат |-align="right"| 1 4 3 2 '''2''' 0 3 4| 4 1 3 2 0 '''2''' 3 4| 4 1 3 2 '''0''' 2 3 4| 4 1 3 2 '''1''' 2 3 4| 4 1 3 2 '''1''' 2 3 4| '''1 2 3 4''' '''2 4 3 1''' |- !colspan="8"| Итоговый массив|-|align="center" colspan="8"|<font color="red">2 4 3 1</font>|}</center> Почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении <tex>Quicksort</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива(выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента). Таким образом, так как каждый раз массив разбивается на две части - большие или равные опорному элементы и меньшие его - на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались.
===Среднее время работы===
{{
