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

Эта статья находится в разработке!

Быстрая сортировка(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы [math]O(nlogn)[/math], что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.

Алгоритм

• Выбираем опорный элемент.
• Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее.
• Рекурсивно сотрируем "маленькие" и "большие" элементы.

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

В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь [math]O(n)[/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].

Ссылки

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

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

Литература

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