Изменения
→Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента
==Алгоритм==
===Оптимизация глубины рекурсии до O(logn) в худшем случаеРазбиение массива===В случае повторяющихся неудачных разбиений опорным элементомОсновной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> типа <tex> T </tex> нужным образом.Разбиение осуществляется с использованием следующей стратегии. Прежде всего, глубина рекурсии может достичь в качестве разделяющего элемента произвольно выбирается элемент <Textex>Oa[(nl + r)/ 2] </Textex>. Этого можно избежатьДалее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, если пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в цикле разбивать массивразделенном массиве, но рекурсивно вызываться только и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от частилевого указателя не осталось ни одного элемента, содержащей меньшее число элементовкоторый был бы больше по значению разделяющего, а большую часть продолжать разбивать в циклеи ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.
Переменная <tex> v </tex> сохраняет значение разделяющего элемента <tex> a[(l + r) / 2] </tex>, a <tex> i </tex> и <tex> j </tex> представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение <tex> i </tex> и уменьшает значение <tex> j </tex> на <tex> 1 </tex>, причем условие, что ни один элемент слева от <tex> i </tex> не больше <tex> v </tex> и ни один элемент справа от <tex> j </tex> не меньше <tex> v </tex>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается.
'''int''' partition(a: '''T'''[n], '''int''' l, '''int''' r) '''T''' v = a[(l + r) / 2] '''int''' i = l '''int''' j = r '''while''' (i <tex> \leqslant </tex> j) '''while''' (a[i] < v) i++ '''while''' (a[j] > v) j-- '''if''' (i <tex> \geqslant </tex> j) '''break''' swap(a[i++], a[j--]) '''return''' j ==СсылкиАсимптотика==http===Худшее время работы===Предположим, что мы разбиваем массив так, что одна часть содержит <tex>n - 1</tex> элементов, а вторая {{---}} <tex>1</tex>. Поскольку процедура разбиения занимает время <tex>\Theta(n)</tex>, для времени работы <tex>T(n)</tex> получаем соотношение: <tex>T(n) = T(n - 1) + \Theta(n) = \sum\limits_{k=1}^{n} \Theta(k) = \Theta(\sum\limits_{k=1}^{n} k) = \Theta(n^2)</tex>. Мы видим, что при максимально несбалансированном разбиении время работы составляет <tex>\Theta(n^2)</tex>. В частности, это происходит, если массив изначально отсортирован. ===Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного===В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает <tex>\Theta(n^2)</tex> сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться <tex>1</tex>, а в другом <tex> n - 1 </tex> элемент). Заполним сначала массив <tex>a</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </rutex>, затем применим следующий алгоритм (нумерация с нуля): '''void''' antiQsort(a: '''T'''[n]) '''for''' i = 0 '''to''' n - 1 swap(a[i], a[i / 2])Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.wikipedia При выполнении <tex>\mathrm{partition}</tex> делается <tex>\Theta(n)</tex> сравнений из-за того, что с помощью индексов <tex>i</tex> и <tex>j</tex> мы проходим в лучшем случае <tex>\Omega(n)</tex> элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае <tex>O(2n)</tex> элементов (если оба индекса полностью проходят массив).orgПри каждом изменении индекса делается сравнение, значит, процедура <tex>\mathrm{partition}</wikitex> делает <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> сравнений для массива, построенного таким способом. ===Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента=== Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае {{---}} <tex>\Theta(n^2)</tex>) количество сравнений. Такое число сравнений достигается при разбиении на массивы длиной <tex>1</tex> и <tex>n-1</tex> на каждой итерации. Создадим массив <tex>a</tex> длины <tex>n</tex>, заполненный элементами типа <tex>pair</tex>. Такой элемент хранит пару значений <tex>(val, key)</tex>, где <tex>val</tex> {{---}} элемент массива, а <tex>key</tex> {{---}} индекс. Изначально <tex>a[i]</tex> элемент имеет вид <tex>(0, i)</tex>. Далее, запустим для данного массива алгоритм быстрой сортировки. Сравниваем два элемента типа <tex>pair</tex> по их значениям <tex>val</tex>. На каждом шаге будем выполнять следующие действия: при обращении к <tex>i</tex>-ому элементу в качестве опорного на шаге под номером <tex>k</tex>, присвоим <tex>val = n-k+1</tex> для элемента <tex>a[i]</tex>. Затем выполним шаг сортировки. После завершения работы алгоритма быстрой сортировки, дополнительно отсортируем получившиеся элементы <tex>pair</tex> по значениям <tex>key</tex>. Искомым будет являться массив элементов <tex>val</tex> в соответствующей последовательности.