Smoothsort - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:26:14Z

rollbackEdits.php mass rollback

103.251.167.21 в 04:57, 1 сентября 2022

2022-09-01T04:57:54Z

Shersh: /* Примечание */

2015-06-15T20:53:46Z

‎Примечание

Novik: /* Основная идея */

2015-05-26T18:46:36Z

‎Основная идея

Shersh в 15:09, 20 апреля 2015

2015-04-20T15:09:41Z

5.18.60.192: /* Получение отсортированного массива */

2015-04-16T14:34:14Z

‎Получение отсортированного массива

Shersh: /* Восстановление свойств последовательности */

2015-04-16T14:34:06Z

‎Восстановление свойств последовательности

Shersh: /* Операции над последовательностью куч */

2015-04-16T14:29:45Z

‎Операции над последовательностью куч

Shersh: /* Основная идея */

2015-04-16T14:28:35Z

‎Основная идея

Shersh: /* Связь с быстрой сортировкой */

2015-04-16T14:27:48Z

‎Связь с быстрой сортировкой

@@ Строка 1: / Строка 1: @@
 '''Плавная сортировка''' (англ. Smooth sort) {{---}} алгоритм сортировки, модификация [[Сортировка кучей|сортировки кучей]], разработанный Э. Дейкстрой. Как и пирамидальная сортировка, в худшем случае работает за время <tex> \Theta(N\log{N}) </tex>. Преимущество плавной сортировки в том, что её время работы приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей время работы не зависит от состояния входных данных.
@@ Строка 99: / Строка 78: @@
 === Уменьшение последовательности куч путём удаления элемента справа ===
 Если размер крайней правой кучи равен <tex dpi = 120> 1 </tex> (то есть <tex dpi = 120> L(1) </tex> или <tex dpi = 120> L(0) </tex>), эта куча просто удаляется.
-В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.
+В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.
 Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то восстановление свойства последовательности выполняется за <tex dpi = 120> O(\log{N}) </tex>.

@@ Строка 1: / Строка 1: @@
 '''Плавная сортировка''' (англ. Smooth sort) {{---}} алгоритм сортировки, модификация [[Сортировка кучей|сортировки кучей]], разработанный Э. Дейкстрой. Как и пирамидальная сортировка, в худшем случае работает за время <tex> \Theta(N\log{N}) </tex>. Преимущество плавной сортировки в том, что её время работы приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей время работы не зависит от состояния входных данных.
@@ Строка 78: / Строка 99: @@
 === Уменьшение последовательности куч путём удаления элемента справа ===
 Если размер крайней правой кучи равен <tex dpi = 120> 1 </tex> (то есть <tex dpi = 120> L(1) </tex> или <tex dpi = 120> L(0) </tex>), эта куча просто удаляется.
-В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.
+В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.
 Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то восстановление свойства последовательности выполняется за <tex dpi = 120> O(\log{N}) </tex>.

@@ Строка 124: / Строка 124: @@
 * [[Быстрая сортировка|Быстрая сортировка]]
-==Примечание==
+==Примечания==
 <references />

@@ Строка 17: / Строка 17: @@
 {{Утверждение
-|statement= Любое натуральное число можно представимо в виде суммы <tex dpi = 120> O(\log{N}) </tex> различных чисел Леонардо.
+|statement= Любое натуральное число представимо в виде суммы <tex dpi = 120> O(\log{N}) </tex> различных чисел Леонардо.
 }}

← Предыдущая		Версия 15:09, 20 апреля 2015
Строка 1:		Строка 1:
−	'''Плавная сортировка''' (англ. Smooth sort) {{---}} алгоритм сортировки, модификация [[Сортировка кучей\|сортировки кучей]], разработанный Э. Дейкстрой. Как и пирамидальная сортировка, в худшем случае работает за время <tex> \Theta(N\log{N}) </tex>. Преимущество плавной сортировки в том, что её ~~сложность~~ приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей ~~сложность всегда одна, независимо~~ от состояния входных данных.	+	'''Плавная сортировка''' (англ. Smooth sort) {{---}} алгоритм сортировки, модификация [[Сортировка кучей\|сортировки кучей]], разработанный Э. Дейкстрой. Как и пирамидальная сортировка, в худшем случае работает за время <tex> \Theta(N\log{N}) </tex>. Преимущество плавной сортировки в том, что её время работы приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей время работы не зависит от состояния входных данных.

	==Основная идея==		==Основная идея==

@@ Строка 101: / Строка 101: @@
 ===Получение отсортированного массива===
-Так как удаление максимального элемента из последовательности выполняется за <tex> O(\log n), то время работы сортировки составляет <tex dpi = 120> O(N\log{N}) </tex>.
+Так как удаление максимального элемента из последовательности выполняется за <tex dpi = 120> O(\log{N}) </tex>, то время работы сортировки составляет <tex dpi = 120> O(N\log{N}) </tex>.
 ===Лучший случай===

@@ Строка 84: / Строка 84: @@
 ===Восстановление свойств последовательности===
-Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции '''''prev''''' (возвращает индекс корня ближайшей слева кучи), '''''left''''' (возвращает индекс левого сына), '''''right''''' (возвращает индекс правого сына) уже реализованы. В функцию '''''ensureSequence''''' передается индекс корня кучи, с которой начинаем восстановление.
+Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции <tex>\mathrm{prev}</tex> (возвращает индекс корня ближайшей слева кучи), <tex>\mathrm{left}</tex> (возвращает индекс левого сына), <tex>\mathrm{right}</tex> (возвращает индекс правого сына) уже реализованы. В функцию <tex>\mathrm{ensureSequence}</tex> передается индекс корня кучи, с которой начинаем восстановление.
 <code>
   '''function''' ensureSequence(i: '''int'''):

@@ Строка 55: / Строка 55: @@
 При конструировании последовательности куч будем по очереди вставлять в конец новые элементы, а при получении отсортированного массива {{---}} удалять максимальный элемент из последовательности. Следовательно, нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что в начале последовательности располагаются кучи максимального размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности.
-Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти индекс корня соседней кучи слева от неё. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <tex dpi = 120> (n - 1) </tex>-ая, а правым является <tex dpi = 120> (n - 2) </tex>-ая куча Леонардо. Для хранения списка длин куч придется выделить <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти.
+Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти индекс корня кучи слева от неё. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <tex dpi = 120> (n - 1) </tex>-ая, а правым является <tex dpi = 120> (n - 2) </tex>-ая куча Леонардо. Для хранения списка длин куч придется выделить <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти.
 ===Вставка элемента===

@@ Строка 118: / Строка 118: @@
 ===Связь с быстрой сортировкой===
-На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в худшем случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку. Так реализована стандартная сортировка в стандартной библиотеке языка С++. Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы на некоторых тестах, так как после нескольких итераций быстрой сортировки массив окажется почти отсортированным, а на таких массивах время работы плавной сортировки приближается к линейному. Хотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для сортировки сравнениями | теореме о нижней оценке]].
+На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в худшем случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку. Так реализована сортировка в стандартной библиотеке языка С++. Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы на некоторых тестах, так как после нескольких итераций быстрой сортировки массив окажется почти отсортированным, а на таких массивах время работы плавной сортировки приближается к линейному. Хотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для сортировки сравнениями | теореме о нижней оценке]].
 ==См. также==