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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основная идея)
Строка 1: Строка 1:
'''''Smoothsort''''' (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную <tex dpi = 120> O(n log n) </tex>. Преимущество плавной сортировки в том, что её сложность приближается к <tex dpi = 120> O(n) </tex>, если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.
+
'''Плавная сортировка''' (англ. Smooth sort) -- алгоритм сортировки, разновидность [[Сортировка кучей|сортировки кучей]], разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную <tex dpi = 120> O(N log N) </tex>. Преимущество плавной сортировки в том, что её сложность приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.
=Основная идея=
+
==Основная идея==
 
Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:
 
Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:
  
Строка 7: Строка 7:
 
Вот первые несколько членов этой последовательности:
 
Вот первые несколько членов этой последовательности:
 
<tex dpi = 120> 1, 3, 5, 9, 15, 25, 41, ... </tex>
 
<tex dpi = 120> 1, 3, 5, 9, 15, 25, 41, ... </tex>
 +
 +
{{Утверждение
 +
|statement= Любое натуральное число представить суммой из <tex dpi = 120> O(log N) </tex> различных чисел Леонардо.
 +
}}
 +
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 17: Строка 22:
  
 
Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом корни деревьев идут в порядке возрастания слева направо.
 
Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом корни деревьев идут в порядке возрастания слева направо.
 
+
При этом не существует двух куч, имеющих одинаковый размер. Так же никакие две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи.  
При этом не существует двух куч, имеющих одинаковый размер.  
 
Это утверждение можно доказать так: Числа Леонардо растут медленнее функции <tex dpi =120> 2^N </tex>, поэтому для любого массива можно найти такое число Леонардо, которое будет больше середины. Исключением является массив длины 2.
 
 
 
Так же никакие две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи.  
 
 
Если мы будем использовать подряд две кучи размерностью <tex dpi = 120> L(x) </tex> и <tex dpi = 120> L(x+1) </tex>, то их можно будет заменить одной – размерностью <tex dpi = 120> L(x+2) </tex>.
 
Если мы будем использовать подряд две кучи размерностью <tex dpi = 120> L(x) </tex> и <tex dpi = 120> L(x+1) </tex>, то их можно будет заменить одной – размерностью <tex dpi = 120> L(x+2) </tex>.
  
Строка 27: Строка 28:
 
* Конструирование последовательности куч
 
* Конструирование последовательности куч
 
* Пока последовательность куч не пустая достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
 
* Пока последовательность куч не пустая достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
 +
 +
==Операции==
 +
Необходимы две операции: увеличение последовательности куч путём добавления элемента справа и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности куч.
 +
===Вставка элемента===
 +
* Если две последние кучи имеют размеры <tex dpi = 120> L(x + 1) </tex> и <tex dpi = 120> L(x) </tex> (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного <tex dpi = 120> L(x+2) </tex>. Для неё свойство кучи необязательно.
 +
* Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером 1. Этот размер полагается равным <tex dpi = 120> L(1) </tex>, кроме случая, когда крайняя правая куча уже имеет размер <tex dpi = 120> L(1) </tex>, тогда размер новой одноэлементной кучи полагают равным <tex dpi = 120> L(0) </tex>.
 +
После этого должно быть восстановлено выполнение свойств кучи и последовательности куч, что, как правило, достигается при помощи разновидности [[Сортировка вставками|сортировки вставками]]:
 +
# Крайняя правая куча (сформированная последней) считается «текущей» кучей.
 +
# Пока слева от неё есть куча и значение её корня больше значения текущего корня и обоих корней куч-потомков:
 +
#* Меняются местами новый корень и корень кучи слева (что не нарушит свойство для текущей кучи). Эта куча становится текущей.
 +
# Выполняется «просеивание», чтобы выполнялось свойство кучи:
 +
#* Пока размер текущей кучи больше 1 и значение корня любой из куч-потомков больше значения корня текущей кучи:
 +
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
 +
Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
 +
 +
Так как в последовательности <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>.
 +
 +
=== Уменьшение последовательности куч путём удаления элемента справа ===
 +
Если размер крайней правой кучи равен 1 (то есть <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>.
 +
 +
==Сложность==
 +
Во время построения последовательности куч <tex dpi = 120> O(N) </tex> раз выполняется вставка элемента. И потом ещё <tex dpi = 120> O(N) </tex> раз выполняется удаление элемента при процедуре получения отсортированного массива. Таким образом сложность плавной сортировки составляет <tex dpi = 120> O(N log N) </tex>.
 +
 +
Однако если подать на вход плавной сортировке уже отсортированный массив асимптотика будет составлять <tex dpi = 120> O(N) </tex>. Дело в том, что во время процедуры получения последовательности куч мы всегда будем вставлять элемент, который больше остальных уже находящихся в последовательности. Поэтому восстановление свойства последовательности будет выполняться за <tex dpi = 120> O(1) </tex> (так как алгоритм только посмотрит на корень соседней кучи, а просеивание закончится сразу потому что новый элемент будет больше своих детей). Операция получения и удаления максимального элемента будет тоже выполняться за <tex dpi = 120> O(1) </tex>, потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи. В итоге, так как алгоритм <tex dpi =120> O(N) </tex> раз вставляет, а потом и удаляет элементы, получается асимптотика <tex dpi = 120> O(N) </tex>.
 +
 +
===Достоинства===
 +
* худшее время работы -- <tex dpi = 120> O(N) </tex>
 +
* время работы в случае, когда подается отсортированный массив -- <tex dpi = 120> O(N) </tex>
 +
 +
===Недостатки===
 +
* не является устойчивой
 +
* требует <tex dpi = 120> O(N) </tex> дополнительной памяти для хранения последовательности куч
 +
 +
==Источники информации==
 +
* [https://en.wikipedia.org/wiki/Smoothsort Wikipedia -- Smoothsort]
 +
* [http://www.keithschwarz.com/smoothsort/ Smoothsort Demystified]
 +
* [http://habrahabr.ru/post/133996/ Хабрахабр -- И снова про сортировки]
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Сортировки]]

Версия 23:04, 28 марта 2015

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

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

Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:

[math] L(0) = 1, L(1) = 1, L(i) = L(i - 1) + L(i - 2) + 1 [/math]

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

Утверждение:
Любое натуральное число представить суммой из [math] O(log N) [/math] различных чисел Леонардо.


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


Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом корни деревьев идут в порядке возрастания слева направо. При этом не существует двух куч, имеющих одинаковый размер. Так же никакие две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи. Если мы будем использовать подряд две кучи размерностью [math] L(x) [/math] и [math] L(x+1) [/math], то их можно будет заменить одной – размерностью [math] L(x+2) [/math].

Алгоритм представляет из себя несколько стадий:

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

Операции

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

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

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

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

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

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

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

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

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

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

Сложность

Во время построения последовательности куч [math] O(N) [/math] раз выполняется вставка элемента. И потом ещё [math] O(N) [/math] раз выполняется удаление элемента при процедуре получения отсортированного массива. Таким образом сложность плавной сортировки составляет [math] O(N log N) [/math].

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

Достоинства

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

Недостатки

  • не является устойчивой
  • требует [math] O(N) [/math] дополнительной памяти для хранения последовательности куч

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