76
правок
Изменения
Нет описания правки
{{В разработке}}
'''Быстрая сортировка'''(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за <Tex>O(n^2)</Tex>, среднее Среднее время работы <Tex>O(nlogn)</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.
==Алгоритм==
==Асимптотика==
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
http://en.wikipedia.org/wiki/Quicksort
==Литература==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 7
