65
правок
Изменения
Worst case when middle element is chosen added
Мы видим, что при максимально несбалансированном разбиении время работы составляет <tex>\Theta(n^2)</tex>. В частности, это происходит, если массив изначально отсортирован.
===Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного===
В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает максимальное количество (<tex>\Theta(n^2)</tex>) сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться <tex>1</tex>, а в другом <tex> n - 1 </tex> элемент).
Заполним сначала массив длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с единицы):
'''for''' i = 1 to n
swap(a[i],a[i/2])
Таким образом на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.
При выполнении <tex>\mathrm{partition}</tex> на каждом шаге делается <tex>\Theta(n)</tex> сравнений. Таких шагов будет <tex>\Theta(n)</tex>, потому что разбиение производится на массивы длины <tex>1</tex> и <tex> n - 1 </tex> (так как на каждом шаге средний элемент является самым крупным). Следовательно, на массиве, который строится описанным выше способом, быстрая сортировка делает максимальное количество сравнений.
===Среднее время работы===
{{
