Изменения
→Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента
'''Быстрая сортировка''' (qsortангл. ''quick sort'', сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.
==Алгоритм==
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй". * из массива выбирается некоторый опорный Массив <tex> a[l \ldots r]</tex> типа <tex> T </tex> разбивается на два (возможно пустых) подмассива <tex> a[l \ldots q]</tex> и <tex> a[q+1 \ldots r]</tex>, таких, что каждый элемент <tex>a[il \ldots q]</tex>меньше или равен <tex> a[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> a[q+1 \ldots r]</tex>. Индекс вычисляется в ходе процедуры разбиения.* запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные Подмассивы <tex>a[il \ldots q]</tex>, влево от него, а все ключи, большие, либо равные и <tex>a[iq+1 \ldots r]</tex> {{---}} вправосортируются с помощью рекурсивного вызова процедуры быстрой сортировки.* Поскольку подмассивы сортируются на месте, для обоих подмассивових объединения не требуются никакие действия: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.весь массив <tex> a[l \ldots r]</tex> оказывается отсортированным.
==Псевдокод==
'''functionvoid''' quicksort(Aa: '''T'''[n], '''int''' l, '''int''' r):
'''if''' l < r
'''int''' q = partition(Aa, l, r) quicksort(Aa, l, q - 1) quicksort(Aa, q + 1, r)Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(Aa, 0, length[Aa] - 1)}</tex>.
===Разбиение массива===
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>Aa[pl \ldots r]</tex> типа <tex> T </tex> нужным образом.Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент <tex> a[(l + r) / 2] </tex>. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами.Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента. Переменная <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(Aa: '''T'''[n], '''int''' l, '''int''' r): x '''T''' v = Aa[(l+ r) / 2] '''int''' i = l '''int''' j = r '''while''' ''true'' (i <tex> \leqslant </tex> j) '''while''' A(a[i] < x v) i = i + 1+ '''while''' A(a[j] > x v) j = j - 1- '''if''' (i < tex> \geqslant </tex> j ) '''break''' swap(Aa[i++], Aa[j--]) '''else''' '''return''' j
==Асимптотика==
===Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного===
В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает максимальное количество (<tex>\Theta(n^2)</tex>) сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться <tex>1</tex>, а в другом <tex> n - 1 </tex> элемент). Заполним сначала массив <tex>a</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с нуля): '''void''' antiQsort(a: '''T'''[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> сравнений для массива, построенного таким способом. ===Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента=== Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае {{---}} <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>
===Среднее время работы===
{{
Лемма
|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>
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>
}}
Mатожидание времени работы быстрой сортировки будет <tex>O(n \log n)</tex>.
==УлучшенияМодификации==В случае повторяющихся неудачных разбиений опорным элементом===Нерекурсивная реализация быстрой сортировки===Для выполнения быстрой сортировки можно воспользоваться [[Стек | стеком]], в котором в виде сортируемых подмассивов содержится перечень действий, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подмассива, он выталкивается из стека. После разделения массива получаются два подмассива, требующих дальнейшей обработки, которые и заталкиваются в стек.Представленная ниже нерекурсивная реализация использует стек, заменяя рекурсивные вызовы помещением в стек параметров функции, а вызовы процедур и выходы из них — циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. Мы помещаем больший из двух подмассивов в стек первым с тем, чтобы максимальная глубина рекурсии может достичь стека при сортировке <Textex>O(n)N</Textex>, а время работы алгоритма элементов не превосходила величины <tex>\log n</tex>O. '''void''' quicksort(a: '''T'''[n^2], '''int''' l, '''int''' r) '''stack'''</tex'''pair'''<'''int''','''int'''> >s s.push(l, r) '''while''' (s. Существуют различные способы разбиения массиваisNotEmpty) (l, направленные против худшего случая:r) = s.pop()* При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — '''if''' (r <tex>O(n \log n)leqslant </tex>l) '''continue''' '''int''' i = partition(a, l, r) '''if''' (i - l > r - i) s.push(l, i - 1)* Выбирать опорным элементом средний из трех s.push(первогоi + 1, среднего и последнего элементовr) '''else''' s.push(i + 1, r)* Разбивать массив не на две s.push(l, а на три части.i - 1)
== Источники информации ==
* [[wikipedia:ru:Быстрая сортировка|Википедия {{---}} быстрая Быстрая сортировка]]* [[wikipedia:en:Quicksort|Wikipedia {{---}} Quicksort]]* [[wikipedia:en:Introsort|Wikipedia {{---}} Introsort]]
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ глава 7
* ''Р. Седжвик'': Фундаментальные алгоритмы на С++ части 1 - 4
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]
[[Категория: Сортировки на сравнениях]]