65
правок
Изменения
м
minor
Заполним сначала массив <tex>A</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с нуля):
'''function''' antiQsort (A: '''int'''[n]):
'''for''' i = 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>\mathrm{antiQsort}</tex> на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А <tex>\mathrm{partition}</tex> делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как <tex> \mathrm{antiQsort} </tex> на массиве любой длины будет выполнять операции, обратные <tex>\mathrm{partition}</tex>. Фактически, <tex>\mathrm{partition}</tex> {{---}} это <tex>\mathrm{antiQsort}</tex>, запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала <tex>i</tex> дойдет до середины массива, до опорного элемента, <tex>j</tex> останется равным индексу последнего элемента. Затем произойдет <tex>\mathrm{swap}</tex> и <tex>i</tex> снова начнет увеличиваться, пока не дойдет до последнего элемента, <tex>j</tex> опять не изменит свою позицию. Потом произойдет выход из <tex>\mathrm{while}</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> сравнений для массива, построенного таким способом.
