Изменения

Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае {{- --}} <tex>\Theta(n^2)</tex>) количество сравнений. Такое число сравнений достигается при разбиении на массивы длиной <tex>1</tex> и <tex>n-1</tex> на каждой итерации. Создадим массив <tex>Arra</tex> длины <tex>n</tex>, заполненный элементами типа <tex>pair</tex>. Такой элемент хранит пару значений <tex>(val, key)</tex>, где <tex>val</tex> {{--- }} элемент массива, а <tex>key</tex> {{--- }} индекс. Изначально <tex>Arr(a[i)]</tex> элемент имеет вид <tex>(0, i)</tex>.

Далее, запустим для данного массива алгоритм быстрой сортировки. Сравниваем два элемента типа <tex>pair</tex> по их значениям <tex>val</tex>. На каждом шаге будем выполнять следующие действия: при обращении к <tex>i</tex>-ому элементу в качестве опорного на шаге под номером <tex>k</tex>, присвоим <tex>val(Arr(i)) = n-k+1</tex> для элемента <tex>a[i]</tex>. После чего Затем выполним шаг сортировки. После завершения работы алгоритма быстрой сортировки, искомым будет являться массив из дополнительно отсортируем получившиеся элементы <tex>val(i)pair</tex>, отсортированных по индексам значениям <tex>key(i)</tex>. Искомым будет являться массив элементов <tex>val</tex> в соответствующей последовательности.

  ! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0

|style="text-align: center;"| 1 2 3 4 <br\> 0 '''0''' 0 0 | style="text-align: center;"| 1 2 3 4 <br\> 0 '''4''' 0 0|style="text-align: center;"| 1 4 3 2 <br\> 0 0 0 '''4'''|style="text-align: center;"| 1 4 3 2 <br\> 0 '''0''' 0 4|style="text-align: center;"| 1 4 3 2 <br\> 0 '''3''' 0 4|style="text-align: center;"| 1 3 4 2 <br\> 0 0 '''3''' 4|style="text-align: center;"| 1 3 4 2 <br\> '''0''' 0 3 4

! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || colspan="2" style="vertical-align: middle;" | результатРезультат

|style="text-align: center;"| 1 3 4 2 <br\> '''2''' 0 3 4|style="text-align: center;"| 3 1 4 2 <br\> 0 '''2''' 3 4|style="text-align: center;"| 3 1 4 2 <br\> '''0''' 2 3 4|style="text-align: center;"| 3 1 4 2 <br\> '''1''' 2 3 4|style="text-align: center;"| 3 1 4 2 <br\> '''1''' 2 3 4| colspan="2" style="text-align: center;vertical-align: middle;"| '''1 2 3 4''' <br\> '''2 4 1 3''' 

Почему Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении <tex>Quicksort\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента). Таким образом, так как каждый раз массив разбивается на две части {{- --}} большие или равные опорному элементы и меньшие его {{--- }} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений.