Быстрая сортировка — различия между версиями
| Строка 6: | Строка 6: | ||
* Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее. | * Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее. | ||
* Рекурсивно сотрируем "маленькие" и "большие" элементы. | * Рекурсивно сотрируем "маленькие" и "большие" элементы. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
===Оптимизация глубины рекурсии до O(logn) в худшем случае=== | ===Оптимизация глубины рекурсии до O(logn) в худшем случае=== | ||
Версия 23:37, 15 июня 2011
Эта статья находится в разработке!
Быстрая сортировка(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы , что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.
Содержание
Алгоритм
- Выбираем опорный элемент.
- Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее.
- Рекурсивно сотрируем "маленькие" и "большие" элементы.
Оптимизация глубины рекурсии до O(logn) в худшем случае
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь . Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.
Ссылки
http://ru.wikipedia.org/wiki/Быстрая_сортировка
http://en.wikipedia.org/wiki/Quicksort
Литература
- Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 7
