212
правок
Изменения
м
==См. также==
* [[Сортировка кучей|Сортировка кучей]]
* [[Быстрая сортировка|Быстрая сортировка]]
Нет описания правки
На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в самом плохом случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают сортировку кучей. Так реализована стандартная сортировка в стандартной библиотеке языка С++. Однако чтобы улучшить время работы в некоторых случаях, можно вместо сортировки кучей использовать плавную сортировку.
Использование smoothsort плавной сортировки вместо heapsort сортировки кучей не улучшит итоговую асимптотику, однако за счет того, что в некоторых случаях асимптотика smoothsort стремится к <tex dpi = 120> O(N) </tex> должна уменьшится константа. Из-за этого время работы должно уменьшиться. ==См. также==* [[Сортировка кучей|Сортировка кучей]]* [[Быстрая сортировка|Быстрая сортировка]]
==Примечание==
<references />
==Источники информации==
