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

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

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

Алгоритм

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

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

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

Асимптотика

Oh, boy, here we go!

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

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

Предположим, что [math]T(n) \leq cO(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]Max(q^2+(n-q-1)^2) \leq (n-1)^2[/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

Так как некий ленивый за***нец не собирается делать вики-конспект я его внаглую беру себе =^-^=.