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

Быстрая сортировка (qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы $O(n\logn)$, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из $n$ элементов в худшем случае может составить $\Theta(n^2)$, на практике этот алгоритм является одним из самых быстрых. Кроме того, быстрая сортировка не требует дополнительной памяти.

Алгоритм

• из массива выбирается некоторый опорный элемент $a[i]$.
• запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные $a[i]$, влево от него, а все ключи, большие, либо равные $a[i]$ — вправо.
• для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру..

Псевдокод

<wikitex>

Quicksort(A, p, r)
    if p < r
        then q = Partition(A, p, r)
            Quicksort(A, p, q)
            Quicksort(A, q + 1, r)

</wikitex> Для сортировки всего массива необходимо выполнить процедуру $Quicksort(A, 1, length[A])$.

Разбиение массива

Основной шаг алгоритма сортировки — процедура $Partition$, которая переставляет элементы массива $A[p..r]$ нужным образом: <wikitex>

Partition(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while true
        do repeat j = j - 1
            until A[j] \le x
            repeat i = i + 1
                until A[i] > x
             if i < j
                 then поменять A[i] и A[j]
                 else return j

</wikitex>

Оптимизация глубины рекурсии до O(logn) в худшем случае

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

Асимптотика

Худшее время работы

Обозначим худшее время работы за $T(n)$. Получим рекуррентное соотношение

$T(n) = \max(T(q)+T(n-q-1))+\Theta(n)$,где $0 \leq q \leq n-1$, так как мы разбиваемся на 2 подзадачи.

Предположим, что $T(n) \leq c(n^2)$. Тогда получим

$T(n) \leq \max(cq^2+c(n-q-1)^2)+\Theta(n) = cMax(q^2+(n-q-1)^2)+\Theta(n)$

Заметим, что $q^2+(n-q-1)^2$ принимает максимальное значение на концах интервала [0; n-1], что позволяет нам сделать оценку

$Max(q^2+(n-q-1)^2) \leq (n-1)^2$

Подставим это в наше выражение для $T(n)$

$T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2$

Таким образом $T(n) = O(n^2)$.

Среднее время работы

Лемма:

Пусть Х - полное количество сравнений элементов с опорным за время работы сортировки. Тогда время работы сортировки равно $O(n \log n)$.

Доказательство:

$\triangleright$

Нам необходимо вычислить полное количество сравнений. Переименуем элементы массива как $z_1...z_n$, где $z_i$ наименьший по порядку элемент. Также введем множество $Z_{ij} = \{z_i, z_{i+1}...z_j\}$. Заметим, что сравнеие каждой пары элементов происходит не больше одного раза, так как элемент сравнивается с опорным, а опорный элемент после разбиения больше не будет участвовать в сравнении. Поскольку каждая пара элементов срановается не более одного раза, полное количество сравнений выражается как $X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}$, где $X_{ij} = 1$ если произошло сравнение $z_i$ и $z_j$ и $X_{ij} = 0$, если сравнения не произошло. Применим к обоим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим $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$ сравнивается с $z_j\}$ Осталось вычислить величину $Pr\{z_i$ сравнивается с $z_j\}$ - вероятность того, что $z_i$ сравнивается с $z_j$. Поскольку предполагается, что все элементы в массиве различны, то при выборе $x$ в качестве опорного элемента впоследствии не будут сравниваться никакие $z_i$ и $z_j$ для которых $z_i \lt x \lt z_j$. С другой стороны, если $z_i$ выбран в качестве опорного, то он будет сравниваться с каждым элементом $Z_{ij}$ кроме себя самого. Таким образом элементы $z_i$ и $z_j$ сравниваются тогда и только тогда когда первым в множестве $Z_{ij}$ опорным элементом был выбран один из них. $Pr\{z_i$ сравнивается с $z_j\} = Pr\{$ первым опорным элементом был $z_i$ или $z_j\} = Pr\{$ первым опорным элементом был $z_i\} + Pr\{$ первым опорным элементом был $z_j\} = \frac {1}{j-i+1} + \frac {1}{j-i+1} = \frac {2}{j-i+1}$ $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} \lt \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)$

$\triangleleft$

Mатожидание времени работы быстрой сортировки будет $O(n \log n)$.

Ссылки

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

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

Литература

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