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

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

Алгоритм

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

Псевдокод

<wikitex>

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

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

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

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

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

</wikitex>

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

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

Асимптотика

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

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

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

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

[math]T(n) \leq \max(cq^2+c(n-q-1)^2)+\Theta(n) = cMax(q^2+(n-q-1)^2)+\Theta(n)[/math]

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

[math]Max(q^2+(n-q-1)^2) \leq (n-1)^2[/math]

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

[math]T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2[/math]

Таким образом [math]T(n) = O(n^2)[/math].

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Ссылки

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

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

Литература

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