11
правок
Изменения
→Способ построить массив с максимальным количеством сравнений при выборе детерминированного элемента в качестве опорного
Разбиение массива будет произведено <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>k</tex>, присвоим для него <tex>val (Arr(i)) = n-ik+1</tex>. После чего выполним шаг сортировки. После завершения работы алгоритма сортировки, искомым будет являться массив из <tex>val(i)</tex>, отсортированных по индексам <tex>key(i)</tex>.
Пример для <tex>n = 4</tex>, при последовательном выборе опорных элементов <tex>2, 2, 1, 1</tex>.
! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0
|-align="right"
|style="text-align: center;"|
1 2 3 4
0 '''0''' 0 0
| style="text-align: center;"|
1 2 3 4
0 '''4''' 0 0
|style="text-align: center;"| 1 4 3 4 2
0 0 0 '''4'''
|style="text-align: center;"| 1 4 3 4 2
0 '''0''' 0 4
|style="text-align: center;"| 1 4 3 2 0 '''3''' 0 4|style="text-align: center;"|
1 3 4 2
0 0 '''3''' 4
|style="text-align: center;"| 1 3 4 3 2
'''0''' 0 3 4
|-
! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || Результатcolspan="2" | результат
|-align="right"
|style="text-align: center;"| 1 3 4 3 2
'''2''' 0 3 4
|style="text-align: center;"| 3 1 4 1 3 2
0 '''2''' 3 4
|style="text-align: center;"| 3 1 4 1 3 2
'''0''' 2 3 4
|style="text-align: center;"| 3 1 4 1 3 2
'''1''' 2 3 4
|style="text-align: center;"| 3 1 4 1 3 2
'''1''' 2 3 4
| colspan="2" style="text-align: center;"|
'''1 2 3 4'''
'''2 4 1 3 1'''
|-
!colspan="8"| Итоговый массив
|-
|align="center" colspan="8"|
<font color="red">2 4 1 3 1</font>
|}
</center>
Почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении <tex>Quicksort</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива(выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента). Таким образом, так как каждый раз массив разбивается на две части - большие или равные опорному элементы и меньшие его - на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений. Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.
===Среднее время работы===
