Изменения
→Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента
==Алгоритм==
==Псевдокод=Оптимизация глубины рекурсии до O= '''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r) '''if''' l < r '''int''' q = partition(a, l, r) quicksort(a, l, q) quicksort(a, q + 1, r)Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(logna, 0, length[a] - 1) в худшем случае}</tex>. ===Разбиение массива===В случае повторяющихся неудачных разбиений опорным элементомОсновной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, глубина рекурсии может достичь которая переставляет элементы массива <Textex>Oa[l \ldots r]</tex> типа <tex> T </tex> нужным образом.Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент <tex> a[(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
==Асимптотика==
===Худшее время работы===
Мы видим, что при максимально несбалансированном разбиении время работы составляет <tex>T(n) = Max(T(q)+T(n-q-1))+\Theta(n^2)</tex>. В частности,где <tex>0 \leq q \leq n-1</tex>это происходит, так как мы разбиваемся на 2 подзадачиесли массив изначально отсортирован.
Заполним сначала массив <tex>a</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex>T(n) \leq Max</tex>, затем применим следующий алгоритм (cq^2+c(n-q-1нумерация с нуля)^2)+\Theta: '''void''' antiQsort(a: '''T'''[n]) '''for''' i = cMax(q^2+(0 '''to''' n-q-1)^ swap(a[i], a[i / 2])+\Theta(n)</tex>Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.
Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. <tex>Max(q^2+(n\mathrm{antiQsort}</tex> на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А <tex>\mathrm{partition}</tex> делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как <tex> \mathrm{antiQsort} </tex> на массиве любой длины будет выполнять операции, обратные <tex>\mathrm{partition}</tex>. Фактически, <tex>\mathrm{partition}</tex> {{--q-1)^2) }} это <tex>\mathrm{antiQsort}</tex>, запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала <tex>i</tex> дойдет до середины массива, до опорного элемента, <tex>j</tex> останется равным индексу последнего элемента. Затем произойдет <tex>\leq (n-1)^2mathrm{swap}</tex> и <tex>i</tex> снова начнет увеличиваться, пока не дойдет до последнего элемента, <tex>j</tex> опять не изменит свою позицию. Потом произойдет выход из <tex>\mathrm{while}</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> в соответствующей последовательности. Пример для <tex>n = 4</tex>, при последовательном выборе опорных элементов <tex>2, 2, 1, 1</tex>. <center> {| class="wikitable"!colspan="8"| Построение массива |- ! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0|-align="right"|style="text-align: center;"|1 2 3 4 <br> 0 '''0''' 0 0| style="text-align: center;"|1 2 3 4 <br> 0 '''4''' 0 0|style="text-align: center;"|1 4 3 2 <br> 0 0 0 '''4'''|style="text-align: center;"|1 4 3 2 <br> 0 '''0''' 0 4|style="text-align: center;"|1 4 3 2 <br> 0 '''3''' 0 4|style="text-align: center;"|1 3 4 2 <br> 0 0 '''3''' 4|style="text-align: center;"|1 3 4 2 <br> '''0''' 0 3 4|-! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || colspan="2" style="vertical-align: middle;"| Результат |-align="right"|style="text-align: center;"|1 3 4 2 <br> '''2''' 0 3 4|style="text-align: center;"|3 1 4 2 <br> 0 '''2''' 3 4|style="text-align: center;"|3 1 4 2 <br> '''0''' 2 3 4|style="text-align: center;"|3 1 4 2 <br> '''1''' 2 3 4|style="text-align: center;"|3 1 4 2 <br> '''1''' 2 3 4| colspan="2" style="text-align: center;vertical-align: middle;" |'''1 2 3 4''' <br> '''2 4 1 3''' |- !colspan="8" | Итоговый массив|-|align="center" colspan="8"|<font color="red">2 4 1 3</font>|}</center> Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу максимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента). Таким образом , так как каждый раз массив разбивается на две части {{---}} большие или равные опорному элементы и меньшие его {{---}} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>T\Theta(n^2) = O</tex> сравнений. Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.
===Среднее время работы===
{{
Лемма
|statement=Пусть Х - полное количество сравнений элементов с опорным за время работы сортировки. Тогда время Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.|proof=Пусть <tex>X</tex> {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.Переименуем элементы массива как <tex>z_1...\ldots z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...\ldots z_j\}</tex>. Заметим, что сравнение каждой пары элементов происходит не больше одного раза, так как элемент сравнивается с опорным, а опорный элемент после разбиения больше не будет участвовать в сравнении.
Поскольку каждая пара элементов срановается сравнивается не более одного раза, полное количество сравнений выражается как
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex> если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex> и <tex>X_{ij} = 0</tex>, если сравнения не произошло.
Применим к обоим обеим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим
<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>
Осталось вычислить величину <tex>Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>{{---}} вероятность того, что <tex>z_i</tex> сравнивается с <tex>z_j</tex>. Поскольку предполагается, что все элементы в массиве различны, то при выборе <tex>x</tex> в качестве опорного элемента впоследствии не будут сравниваться никакие <tex>z_i</tex> и <tex>z_j</tex> для которых <tex>z_i < x < z_j</tex>. С другой стороны, если <tex>z_i</tex> выбран в качестве опорного, то он будет сравниваться с каждым элементом <tex>Z_{ij}</tex> кроме себя самого. Таким образом элементы <tex>z_i</tex> и <tex>z_j</tex> сравниваются тогда и только тогда когда первым в множестве <tex>Z_{ij}</tex> опорным элементом был выбран один из них.
<tex>Pr\{z_i</tex> сравнивается с <tex>z_j\} =
Pr\{</tex> первым опорным элементом был <tex>z_i</tex> или <tex>z_j\} = Pr\{</tex> первым опорным элементом был <tex>z_i\} +Pr\{</tex> первым опорным элементом был <tex>z_j\} =</tex><tex> =\frac dfrac {1}{j-i+1} + \frac dfrac {1}{j-i+1} = \frac dfrac {2}{j-i+1} </tex>
<tex> E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \frac dfrac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac dfrac 2{k+1} < \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac dfrac 2{k} </tex> <tex>= \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n)</tex>
}}