635
правок
Изменения
→Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного
В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает <tex>\Theta(n^2)</tex> сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться <tex>1</tex>, а в другом <tex> n - 1 </tex> элемент).
Заполним сначала массив <tex>Aa</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с нуля):
'''void''' antiQsort(a: '''int'''[n]):
'''for''' i = 0 '''to''' n - 1
swap(a[i], Aa[i / 2])
Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.
