Smoothsort — различия между версиями
(Новая страница: «'''''Smoothsort''''' (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сор...») |
|||
| Строка 1: | Строка 1: | ||
'''''Smoothsort''''' (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную <tex dpi = 120> O(n log n) </tex>. Преимущество плавной сортировки в том, что её сложность приближается к <tex dpi = 120> O(n) </tex>, если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных. | '''''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> | ||
Версия 23:20, 13 марта 2015
Smoothsort (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную . Преимущество плавной сортировки в том, что её сложность приближается к , если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.
Основная идея
Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:
