Быстрая сортировка

2012-06-05T14:33:52Z

178.178.28.57: /* Среднее время работы */

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

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

==Псевдокод==
<wikitex>
Quicksort(A, p, r)
if p < r
then q = Partition(A, p, r)
Quicksort(A, p, q)
Quicksort(A, q + 1, r)
</wikitex>
Для сортировки всего массива необходимо выполнить процедуру <tex>Quicksort(A, 1, length[A])</tex>.

===Разбиение массива===
Основной шаг алгоритма сортировки {{---}} процедура <tex>Partition</tex>, которая переставляет элементы массива <tex>A[p..r]</tex> нужным образом:
<wikitex>
Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
do repeat j = j - 1
until A[j] <tex>\leq</tex> x
repeat i = i + 1
until A[i] > x
if i < j
then поменять A[i] и A[j]
else return j
</wikitex>

==Асимптотика==
===Худшее время работы===
Предположим, что мы разбиваем массив так, что одна часть содержит <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>. В частности, это происходит, если массив изначально отсортирован.

===Среднее время работы===
{{
Лемма
|statement=Пусть Х {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Тогда время работы сортировки равно <tex>O(n \log n)</tex>.
|proof=Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1...z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...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\} =
\frac {1}{j-i+1} + \frac {1}{j-i+1} = \frac {2}{j-i+1} </tex>

<tex> E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \frac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k+1} < \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \frac 2{k} = \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n)</tex>
}}
Mатожидание времени работы быстрой сортировки будет <tex>O(n \log n)</tex>.

==Способы разбиения массива==
* При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(''n'' lg ''n'').
* Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов). Такой выбор также направлен против худшего случая.
* Разбивать массив не на две, а на три части.

==Оптимизация глубины рекурсии до O(logn) в худшем случае==
Время работы алгоритма сортировки зависит от того, как разбивается массив на каждом шаге. В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex> а время работы алгоритма <tex>O(n^2)</tex>. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.

== Ссылки ==
* http://ru.wikipedia.org/wiki/Быстрая_сортировка

* http://en.wikipedia.org/wiki/Quicksort

==Литература==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 7

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

Викиконспекты - Вклад участника [ru]

Быстрая сортировка