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

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

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

Алгоритм

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

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

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

Асимптотика

Oh, boy, here we go!

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

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

Ссылки

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

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

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