1632
правки
Изменения
м
rollbackEdits.php mass rollback
</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>.
