Быстрая сортировка — различия между версиями
м |
|||
| Строка 1: | Строка 1: | ||
| − | '''Быстрая сортировка''' - | + | {{В разработке}} |
| + | '''Быстрая сортировка'''(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за <Tex>O(n^2)</Tex>, среднее время работы <Tex>O(nlogn)</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. | ||
==Алгоритм== | ==Алгоритм== | ||
| − | ===Оптимизация глубины рекурсии до O(logn)=== | + | 1)Выбираем опорный элемент. |
| + | 2)Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее. | ||
| + | 3)Рекурсивно сотрируем "маленькие" и "большие" элементы. | ||
| + | |||
| + | ===Оптимизация глубины рекурсии до O(logn) в худшем случае=== | ||
| + | В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex>. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле. | ||
==Асимптотика== | ==Асимптотика== | ||
| + | Oh, boy, here we go! | ||
| + | |||
==Ссылки== | ==Ссылки== | ||
http://ru.wikipedia.org/wiki/Быстрая_сортировка | http://ru.wikipedia.org/wiki/Быстрая_сортировка | ||
| Строка 9: | Строка 17: | ||
http://en.wikipedia.org/wiki/Quicksort | http://en.wikipedia.org/wiki/Quicksort | ||
| − | Так как некий ленивый за***нец не собирается делать вики-конспект я его внаглую беру себе =^-^= | + | Так как некий ленивый за***нец не собирается делать вики-конспект я его внаглую беру себе =^-^=. |
Версия 19:33, 7 июня 2011
Эта статья находится в разработке!
Быстрая сортировка(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за , среднее время работы , что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.
Содержание
Алгоритм
1)Выбираем опорный элемент. 2)Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее. 3)Рекурсивно сотрируем "маленькие" и "большие" элементы.
Оптимизация глубины рекурсии до O(logn) в худшем случае
В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь . Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.
Асимптотика
Oh, boy, here we go!
Ссылки
http://ru.wikipedia.org/wiki/Быстрая_сортировка
http://en.wikipedia.org/wiki/Quicksort
Так как некий ленивый за***нец не собирается делать вики-конспект я его внаглую беру себе =^-^=.
