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