Изменения

'''Быстрая сортировка''' (qsortангл. ''quick sort'', сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.

* из массива выбирается некоторый опорный элемент <tex>aA[i]</tex>.* запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные <tex>aA[i]</tex>, влево от него, а все ключи, большие, либо равные <tex>aA[i]</tex> {{---}} вправо.

'''function''' quicksort('''int[]''' A, '''int''' l, '''int''' r):

'''int''' partition('''int[]''' A, '''int''' l, '''int''' r):

В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает максимальное количество (<tex>\Theta(n^2)</tex>) сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться <tex>1</tex>, а в другом <tex> n - 1 </tex> элемент).

Заполним сначала массив <tex>A</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с единицынуля): '''function''' antiQsort ('''int[]''' A): '''for''' i = 1 0 '''to ''' n - 1 swap(a[i],a[i/2])Таким образом Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.

При выполнении <tex>\mathrm{partition}</tex> на делается <tex>\Theta(n)</tex> сравнений из-за того, что с помощью индексов <tex>i</tex> и <tex>j</tex> мы проходим в лучшем случае <tex>\Omega(n)</tex> элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае <tex>O(2n)</tex> элементов (если оба индекса полностью проходят массив). При каждом шаге изменении индекса делается сравнение, значит, процедура <tex>\mathrm{partition}</tex> делает <tex>\Theta(n)</tex> сравненийс точностью до константы. Таких шагов  Разбиение массива будет произведено <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> сравненийдля массива, построенного таким способом.