Smoothsort — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Операции над последовательностью куч)
(Операции над последовательностью куч)
Строка 53: Строка 53:
  
 
==Операции над последовательностью куч==
 
==Операции над последовательностью куч==
При конструировании последовательности куч будем последовательно выполнять вставку в конец новых элементов. В итоге мы получим, что наш массив разбит на подмассивы размером <tex dpi = 120> L(k) </tex>. Для каждого подмассива выполним операцию '''heapify'''(она выполняется так же, как в [[Двоичная куча|двоичной куче]]), после которой необходимо будет отсортировать корни куч, чтобы выполнялся инвариант последовательности. Следовательно, нам необходимы четыре операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого размера), уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности, операция сортировки корней куч и восстановление инварианта последовательности.
+
При конструировании последовательности куч будем последовательно выполнять вставку в конец новых элементов, а при операции получении отсортированного массива будем удалять максимальный элемент из последовательности. Следовательно, нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности.
  
 
Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти корень соседней кучи слева. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <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> дополнительной памяти.
  
 
===Вставка элемента===
 
===Вставка элемента===
[[Файл:add-example.png|470px|thumb|right|Пример вставки элемента.]]
+
[[Файл:add-example.png|470px|thumb|right|Пример вставки элемента (без просеивания вниз)]]
[[Файл:Leonardo-heap-2.png|470px|thumb|right|Вставка в последовательность куч, показанную выше, числа 13.]]
+
[[Файл:Leonardo-heap-2.png|470px|thumb|right|Вставка в последовательность куч, показанную выше, числа 13. Далее будет сразу происходить просеивание внутри "зеленого" дерева Леонардо, так как корень соседнего дерева меньше, чем дети корня "зелёного" дерева.]]
 
При добавлении в последовательность нового элемента возможны две ситуации:
 
При добавлении в последовательность нового элемента возможны две ситуации:
  
 
* Если две последние кучи имеют размеры <tex dpi = 120> L(x + 1) </tex> и <tex dpi = 120> L(x) </tex> (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного <tex dpi = 120> L(x+2) </tex>. Для неё свойство кучи необязательно.
 
* Если две последние кучи имеют размеры <tex dpi = 120> L(x + 1) </tex> и <tex dpi = 120> L(x) </tex> (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного <tex dpi = 120> L(x+2) </tex>. Для неё свойство кучи необязательно.
 
* Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером <tex dpi = 120> 1 </tex>. Этот размер полагается равным <tex dpi = 120> L(1) </tex>, кроме случая, когда крайняя правая куча уже имеет размер <tex dpi = 120> L(1) </tex>, тогда размер новой одноэлементной кучи полагают равным <tex dpi = 120> L(0) </tex>.
 
* Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером <tex dpi = 120> 1 </tex>. Этот размер полагается равным <tex dpi = 120> L(1) </tex>, кроме случая, когда крайняя правая куча уже имеет размер <tex dpi = 120> L(1) </tex>, тогда размер новой одноэлементной кучи полагают равным <tex dpi = 120> L(0) </tex>.
Нам не важно выполняется ли в данный момент инвариант кучи, потому что позже мы будем выполнять для неё операцию heapify.
+
После этого должно быть восстановлено выполнение свойств кучи и последовательности куч, что, как правило, достигается при помощи разновидности [[Сортировка вставками|сортировки вставками]] (см. ниже псевдокод):
 
Так как при выполнении вставки мы смотри только на размеры двух последних куч, то вставка выполняется за <tex dpi = 120> O(1) </tex>.
 
 
 
===Сортировка корней куч===
 
 
 
Для сортировки корней будем использовать [[Сортировка выбором|сортировку выбором]]. Пусть в последовательности <tex dpi = 120> l = O(\log{N}) </tex> куч. Сортировать будем с конца, то есть в начале текущей назначается последняя куча. Тогда после первой итерации в самой правой куче мы получим максимальный корень. А кучу, из которой этот корень пришел в текущую, после обмена корнем необходимо просеять. А затем уменьшаем <tex dpi = 120> l </tex> на <tex dpi =120> 1 </tex>. Повторяем эти действия, пока <tex dpi = 120> l </tex> не станет равна <tex dpi =120> 1 </tex>.
 
 
 
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то сортировка вставками работает за <tex dpi =120> O(\log^2{N}) </tex>. Просеивание выполняется за <tex dpi =120> O(\log{N}) </tex>, то в итоге алгоритм работает за <tex dpi =120> O(\log^2{N}) + O(\log{N}) \cdot O(\log{N}) = O(\log^2{N})</tex>
 
 
 
===Восстановление свойств последовательности===
 
 
 
Восстановление свойст, как правило, достигается при помощи разновидности [[Сортировка вставками|сортировки вставками]] (см. ниже псевдокод):
 
 
# Крайняя правая куча (сформированная последней) считается «текущей» кучей.
 
# Крайняя правая куча (сформированная последней) считается «текущей» кучей.
 
# Пока слева от неё есть куча, и значение её корня больше значения текущего корня и обоих корней куч-потомков:
 
# Пока слева от неё есть куча, и значение её корня больше значения текущего корня и обоих корней куч-потомков:
Строка 84: Строка 72:
 
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
 
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
 
Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
 
Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
 +
 +
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то модификация сортировки вставками будет работать за <tex dpi = 120> O(\log{N}) </tex>. Просеивание тоже выполняется за <tex dpi = 120> O(\log{N}) </tex>, тогда в итоге операция вставки выполняется за:
 +
<tex dpi = 120> O(\log{N}) + O(\log{N}) = O(\log{N}) </tex>.
 +
 +
=== Уменьшение последовательности куч путём удаления элемента справа ===
 +
Если размер крайней правой кучи равен <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>.
 +
 +
===Восстановление свойств последовательности===
  
 
Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции '''''prev''''' (возвращает индекс корня ближайшей слева кучи), '''''left''''' (возвращает индекс левого сына), '''''right''''' (возвращает индекс правого сына) уже реализованы. В функцию '''''ensureSequence''''' передается индекс корня кучи, с которой начинаем восстановление.
 
Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции '''''prev''''' (возвращает индекс корня ближайшей слева кучи), '''''left''''' (возвращает индекс левого сына), '''''right''''' (возвращает индекс правого сына) уже реализованы. В функцию '''''ensureSequence''''' передается индекс корня кучи, с которой начинаем восстановление.
Строка 95: Строка 94:
 
   siftDown(i)
 
   siftDown(i)
 
</code>
 
</code>
 
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то модификация сортировки вставками будет работать за <tex dpi = 120> O(\log{N}) </tex>. Просеивание тоже выполняется за <tex dpi = 120> O(\log{N}) </tex>, тогда в итоге операция вставки выполняется за:
 
<tex dpi = 120> O(\log{N}) + O(\log{N}) = O(\log{N}) </tex>.
 
 
=== Уменьшение последовательности куч путём удаления элемента справа ===
 
Если размер крайней правой кучи равен <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>.
 
  
 
==Сложность==  
 
==Сложность==  

Версия 22:10, 11 апреля 2015

Плавная сортировка (англ. Smooth sort) — алгоритм сортировки, модификация сортировки кучей, разработанный Э. Дейкстрой. Как и пирамидальная сортировка, имеет сложность в худшем случае равную [math] O(N\log{N}) [/math]. Преимущество плавной сортировки в том, что её сложность приближается к [math] O(N) [/math], если входные данные частично отсортированы, в то время как у сортировки кучей сложность всегда одна, независимо от состояния входных данных.

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

Будем развивать идею пирамидальной сортировки. Для этого будем использовать не двоичную кучу, а специальную, полученную с помощью чисел Леонардо[1], которые задаются следующим образом:

[math] L(n) = \begin{cases} 1 & \mathrm{if}\ n = 0, \\ 1 & \mathrm{if}\ n = 1, \\ L(n-1)+L(n-2)+1 & \mathrm{if}\ n \gt 1. \\ \end{cases} [/math]

Вот первые несколько членов этой последовательности: [math] 1, 1, 3, 5, 9, 15, 25, 41, ... [/math]

Утверждение:
Любое натуральное число можно представить суммой из [math] O(\log{N}) [/math] различных чисел Леонардо.
Утверждение:
[math] L(n) = 2 \cdot F(n + 1) - 1 [/math], где [math] F(n + 1) [/math][math] (n + 1) [/math]-ое число Фибоначчи.
[math]\triangleright[/math]
Это утверждение доказывается по индукции. База: [math] L(0) = 2 \cdot F(1) - 1 = 1 [/math]. Пусть для [math] n [/math] первых чисел это равенство выполняется. Делаем индуктивный переход: [math] L(n + 1) = L(n) + L(n - 1) + 1 = 2 \cdot F(n + 1) - 1 + 2 \cdot F(n) - 1 + 1 = 2 \cdot F(n + 2) - 1 [/math]. Утверждение доказано.
[math]\triangleleft[/math]


Определение:
K-ая куча Леонардо — это двоичное дерево с количеством вершин [math] L(k) [/math], удовлетворяющее следующим условиям:
  • число, записанное в корне не меньше чисел в поддеревьях,
  • левым поддеревом является [math] (k-1) [/math]-я куча Леонардо,
  • правым — [math] (k-2) [/math]-я куча Леонардо.

Можно заметить, что куча Леонардо очень похожа на биномиальную. Куча Леонардо используется из-за своих свойств.

Пример последовательности куч (список хранит номера чисел Леонардо, соответствующих размерам куч)

Будем поддерживать следующий инвариант:

  • сортируемый массив делится на группу подмассивов,
  • каждый подмассив представляет собой структуру данных — куча,
  • каждая куча имеет размер равный одному из чисел Леонардо,
  • размеры куч строго убывают слева направо,
  • при этом не существует двух куч, имеющих одинаковый размер,
  • значения ключей в корнях деревьев идут в порядке возрастания слева направо,
  • в самих кучах значение в детях меньше либо равно значению в родителе.

В дальнейшем эту группу подмассивов будем называть последовательность куч.

Алгоритм:

Шаг 0: В массиве записаны элементы, которые надо отсортировать.

Шаг 1: Превращение массива в последовательность куч.

Шаг 2: Пока последовательность куч не пустая достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.

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

При конструировании последовательности куч будем последовательно выполнять вставку в конец новых элементов, а при операции получении отсортированного массива будем удалять максимальный элемент из последовательности. Следовательно, нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности.

Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти корень соседней кучи слева. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является [math] (n - 1) [/math]-ая, а правым является [math] (n - 2) [/math]-ая куча Леонардо. Для хранения списка длин куч придется выделить [math] O(\log{N}) [/math] дополнительной памяти.

Вставка элемента

Пример вставки элемента (без просеивания вниз)
Вставка в последовательность куч, показанную выше, числа 13. Далее будет сразу происходить просеивание внутри "зеленого" дерева Леонардо, так как корень соседнего дерева меньше, чем дети корня "зелёного" дерева.

При добавлении в последовательность нового элемента возможны две ситуации:

  • Если две последние кучи имеют размеры [math] L(x + 1) [/math] и [math] L(x) [/math] (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного [math] L(x+2) [/math]. Для неё свойство кучи необязательно.
  • Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером [math] 1 [/math]. Этот размер полагается равным [math] L(1) [/math], кроме случая, когда крайняя правая куча уже имеет размер [math] L(1) [/math], тогда размер новой одноэлементной кучи полагают равным [math] L(0) [/math].

После этого должно быть восстановлено выполнение свойств кучи и последовательности куч, что, как правило, достигается при помощи разновидности сортировки вставками (см. ниже псевдокод):

  1. Крайняя правая куча (сформированная последней) считается «текущей» кучей.
  2. Пока слева от неё есть куча, и значение её корня больше значения текущего корня и обоих корней куч-потомков:
    • Меняются местами новый корень и корень кучи слева (это гарантирует выполнение инварианта для текущей кучи). И куча, с которой произошел обмен, становится текущей.
  3. Потом выполняется «просеивание» кучи, на которой остановилась сортировка корней, чтобы гарантировать выполнение инварианта кучи:
    • Пока размер текущей кучи больше [math] 1 [/math], и значение корня любой из куч-потомков больше значения корня текущей кучи:
      • Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.

Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.

Так как в последовательности [math] O(\log{N}) [/math] куч, то модификация сортировки вставками будет работать за [math] O(\log{N}) [/math]. Просеивание тоже выполняется за [math] O(\log{N}) [/math], тогда в итоге операция вставки выполняется за: [math] O(\log{N}) + O(\log{N}) = O(\log{N}) [/math].

Уменьшение последовательности куч путём удаления элемента справа

Если размер крайней правой кучи равен [math] 1 [/math] (то есть [math] L(1) [/math] или [math] L(0) [/math]), эта куча просто удаляется. В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.

Так как в последовательности [math] O(\log{N}) [/math] куч, то восстановление свойства последовательности выполняется за [math] O(\log{N}) [/math].

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

Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции prev (возвращает индекс корня ближайшей слева кучи), left (возвращает индекс левого сына), right (возвращает индекс правого сына) уже реализованы. В функцию ensureSequence передается индекс корня кучи, с которой начинаем восстановление.

function ensureSequence(i: int):
  j = prev(i) // j - индекс корня соседней кучи
  while A[j] > A[i] and A[j] > A[left(i)] and A[j] > A[right(i)]
    swap(A[j], A[i])
    i = j
    j = prev(i)
  siftDown(i)

Сложность

Построение последовательности

Получение последовательности куч, для которых не выполняется инвариант, очевидно производится за [math] O(N) [/math]. По указанному выше утверждению [math] N [/math] можно представить в виде суммы длин куч. Пусть [math] N = L(k_1) + L(k_2) + ... + L(k_n) [/math], тогда выполнение операции heapify для всех куч выполнится за [math] O(L(k_1)) + O(L(k_2)) + ... + O(L(k_n)) = O(N) [/math]. В итоге построение последовательности выполняется за [math] O(N) + O(N) + O(\log^2{N}) = O(N) [/math].

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

Так как [math] O(N) [/math] выполняется удаление максимального элемента из последовательности, то вся эта операция выполняется за [math] O(N\log{N}) [/math]. Следовательно, сортировка в худшем случае выполняется за [math] O(N\log{N}) [/math].

Однако если подать на вход плавной сортировке уже отсортированный массив, асимптотика будет составлять [math] O(N) [/math]. Дело в том, что операция получения и удаления максимального элемента будет выполняться за [math] O(1) [/math], потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи. В итоге получается асимптотика [math] O(N) [/math].

Достоинства

  • худшее время работы — [math] O(N\log{N}) [/math],
  • время работы в случае, когда подается отсортированный массив — [math] O(N) [/math].

Недостатки

  • не является устойчивой,
  • требует [math] O(\log{N}) [/math] дополнительной памяти для хранения длин куч в последовательности. Однако с помощью некоторых модификации можно получить [math] O(1) [/math] дополнительной памяти.

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

На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в самом плохом случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают сортировку кучей. Так реализована стандартная сортировка в стандартной библиотеке языка С++. Однако чтобы улучшить время работы в некоторых случаях, можно вместо сортировки кучей использовать плавную сортировку.

Может показаться, что если ограничить глубину рекурсии некоторым числом [math] D [/math], независящим от [math] N [/math], то быстрая сортировка может начать работать за линейное время. Это ложное утверждение, потому как легко составить пример, на котором сортировка станет работать дольше. Например, пусть сортировке на вход подан массив из [math] 10^9 \cdot D [/math] элементов. На таком массиве возможна ситуация, когда разделяющий элемент может каждый раз оказываться минимальным или максимальным. Тогда на вход плавная сортировка получит массив из [math] 10^9 [/math] элементов. На таком массиве плавная сортировка в среднем будет работать дольше, чем быстрая сортировка в силу того, что константа спрятанная в О-натации для неё больше.

См. также

Примечание

Источники информации