Изменения
Новая страница: «'''''Smoothsort''''' (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сор...»
'''''Smoothsort''''' (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную <tex dpi = 120> O(n log n) </tex>. Преимущество плавной сортировки в том, что её сложность приближается к <tex dpi = 120> O(n) </tex>, если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.
==Основная идея==
Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:
<tex dpi = 120> L(0) = 1, L(1) = 1, L(i) = L(i - 1) + L(i - 2) + 1 </tex>
==Основная идея==
Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:
<tex dpi = 120> L(0) = 1, L(1) = 1, L(i) = L(i - 1) + L(i - 2) + 1 </tex>
