Викиконспекты - Вклад участника [ru]

Фибоначчиева куча

2018-05-10T18:57:11Z

188.130.155.157: /* Удаление минимального элемента. Исправлена опечатка в удалении элемента из двусвязного списка. */

'''Фибоначчиева куча''' (англ. ''Fibonacci heap'') {{---}} структура данных, отвечающая интерфейсу [[Приоритетные очереди#Операции | приоритетная очередь]]. Эта структура данных имеет меньшую [[Амортизационный анализ#Основные определения | амортизированную сложность]], чем такие приоритетные очереди как [[Биномиальная куча | биномиальная куча]] и [[Двоичная куча | двоичная куча]]. Изначально эта структура данных была разработана Майклом Фридманом<ref>[[wikipedia:en:Michael_Fredman | Майкл Фридман {{---}} Википедия]]</ref> и Робертом Тарьяном<ref>[[wikipedia:en:Robert_Tarjan | Роберт Тарьян {{---}} Википедия]]</ref> при работе по улучшению асимптотической сложности [[Алгоритм Дейкстры | алгоритма Дейкстры]]. Свое название Фибоначчиева куча получила из-за использования некоторых свойств чисел Фибоначчи<ref>[[wikipedia:en:Fibonacci_number | Числа Фибоначчи {{---}} Википедия]]</ref> в [[Амортизационный анализ#Метод потенциалов | потенциальном анализе]] этой реализации.
== Структура ==
Фибоначчиева куча {{---}} набор из [[Дерево, эквивалентные определения | подвешенных деревьев]] удовлетворяющих свойству: каждый предок не больше своих детей(если дерево на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одним из главных преимуществ Фибоначчиевой кучи {{---}} гибкость её структуры из-за того, что на деревья не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.
{{Определение
|definition=
'''Степень вершины''' (англ. ''degree'') {{---}} количество детей данной вершины. Далее будем обозначать как <tex>degree(x)</tex>, где <tex>x</tex> это вершина.
}}
{{Определение
|definition=
'''Степень кучи''' (англ. ''degree'') {{---}} наибольшая степень вершины этой кучи. Далее будем обозначать как <tex>degree(H)</tex>, где <tex>H</tex> это куча.
}}
== Реализация ==
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]
Для возможности быстрого удаления элемента из произвольного места и объединением с другим списком будем хранить их в [[Список#Циклический список | циклическом двусвязном списке]]. Также будем хранить и все уровни поддерева. Исходя из этого структура каждого узла будет выглядеть вот так.
<code style="display:inline-block">
'''struct''' Node
'''int''' key // ключ
'''Node''' parent // указатель на родительский узел
'''Node''' child // указатель на один из дочерних узлов
'''Node''' left // указатель на левый узел того же предка
'''Node''' right // указатель на правый узел того же предка
'''int''' degree // степень вершины
'''boolean''' mark // был ли удален в процессе изменения ключа ребенок этой вершины)
</code>Также стоит упомянуть, что нам нужен указатель только на одного ребенка, поскольку остальные хранятся в двусвязном списке с ним. Для доступа ко всей куче нам тоже нужен всего один элемент, поэтому разумно хранить именно указатель на минимум кучи(он обязательно один из корней), а для получения размера за константное время будем хранить размер кучи отдельно.
<code style="display:inline-block">
'''struct''' fibonacciHeap
'''int''' size // текущее количество узлов
'''Node''' min // указатель на корень дерева с минимальным ключом
</code>
==== Cоздание кучи ====
Инициализация кучи.
<code style="display:inline-block">
'''function''' buildHeap:
min <tex>= \varnothing</tex>
size = 0
</code>
==== Вставка элемента ====
Данная операция вставляет новый элемент в список корней правее минимума и при необходимости меняет указатель на минимум кучи.
<code style="display:inline-block">
'''function''' insert(x: '''int'''):
'''Node''' newNode // создаем новый узел
newNode.key = x // инициализируем ключ нового узла
'''if''' size = 0 // если куче нет элементов, то только что добавленный минимальный
min = newNode
min.left = newNode
min.right = newNode
'''else''' // иначе аккуратно меняем указатели в списке, чтобы не перепутать указатели
'''Node''' prevRight = min.right
min.right = newNode
newNode.left = min
newNode.right = prevRight
prevRight.left = newNode
'''if''' newNode.key < min.key
min = newNode // меняем указатель на минимум, если надо
newNode.parent <tex>= \varnothing</tex>
size++ // не забываем увеличить переменную size 
</code>
==== Получение минимального элемента ====
Получение минимума всей кучи.
<code style="display:inline-block">
'''int''' getMin:
'''return''' min.key
</code>
==== Соедининение двух куч ====
Для сливание двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую два списка вершины, которых подаются ей в качестве аргументов.
<code style="display:inline-block">
'''function''' unionLists(first: '''Node''', second: '''Node'''):
'''Node''' L = first.left // аккуратно меняем указатели местами указатели
'''Node''' R = second.right
second.right = first
first.left = second
L.right = R
R.left = L
</code>
Сливаем два корневых списка в один и обновляем минимум, если нужно.
<code style="display:inline-block">
'''function''' merge(that: '''fibonacciHeap'''):
'''if''' that.size = 0 // если вторая куча пуста, нечего добавлять
'''return'''
'''if''' size = 0 // если наша куча пуста, то результатом будет вторая куча
min = that.min
size = that.size
'''else'''
unionLists(min, that.min) // объединяем два корневых списка
size += that.size
'''if''' min <tex>= \varnothing</tex> '''or''' (that.min <tex> \neq \varnothing</tex> '''and''' that.min < min) // если минимум кучи изменился, то надо обновить указатель
min = that.min
</code>
==== Удаление минимального элемента====
Первая рассматриваемая операция, в ходе которой значительно меняется структура кучи. Здесь используется вспомогательная процедура <tex>consolidate</tex>, благодаря которой собственно и достигается желанная амортизированная оценка. В данном случае <tex> min = \varnothing</tex> не рассматривается и считается нарушением предусловий <tex>deleteMin</tex>
<code style="display:inline-block">
'''int''' deleteMin:
'''Node''' prevMin = min
unionLists(min, min.child) // список детей min объединяем с корневым
'''Node''' L = min.left // аккуратно удаляем min из списка
'''Node''' R = min.right
L.right = R
R.left = L
'''if''' prevMin.right = prevMin // отдельно рассмотрим случай с одним элементом
min <tex>= \varnothing</tex>
'''return'''
min = min.right // пока что перекинем указаиель min на правого сына, а далее consolidate() скорректирует min в процессе выполнения
consolidate()
size--
'''return''' prevMin.key
</code>
===== Прорежение деревьев =====
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более <tex> degree(H) + 1</tex> вершин.

Для этого возьмем массив списков указателей на корни деревьев <tex> A[0 \dots D[H]] </tex>, где <tex> degree(H) </tex> {{---}} максимальная степень вершины в текущем корневом списке.

Затем происходит [[Биномиальная_куча#merge | процесс, аналогичный слиянию биномиальных куч]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке <tex>A</tex> еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку. Подвешиваем мы его следующим образом: в корневой список добавляем корень минимальный из тех двух, а корень другого добавляем в список детей корневой вершины. Чтобы лучше понять этот процесс лучше воспользоваться [https://www.cs.usfca.edu/~galles/visualization/FibonacciHeap.html визуализатором]
<code style="display:inline-block">
'''function''' consolidate:
A = '''Node[]'''
A[min.degree] = min // создаем массив и инициализируем его min
'''Node''' current = min.right
'''while''' A[current.degree] <tex>\neq</tex> current // пока элементы массива меняются
'''if''' A[current.degree] <tex>= \varnothing</tex> // если ячейка пустая, то положим в нее текущий элемент
A[current.degree] = current
current = current.right
'''else''' // иначе подвесим к меньшему из текущего корня и того, который лежит в ячейке другой
'''Node''' conflict = A[current.degree]
'''Node''' addTo, adding
'''if''' conflict.key < current.key
addTo = conflict
adding = current
'''else'''
addTo = current
adding = conflict
unionLists(addTo.child, adding)
adding.parent = addTo
addTo.degree++
current = addTo
'''if''' min.key > current.key // обновляем минимум, если нужно
min = current
</code>
'''Пример'''

Изначально добавляем в нашу кучу <tex>7</tex> элементов <tex>56, 22, 84, 32, 85, 15, 16</tex>. После этого выполним операцию извлечения минимума:

[[File:Fibonacci-heap-consolidate-example-1.png|thumb|center|500px|Начальное состояние кучи]]

* Удалим минимальный элемент из циклического корневого списка и заведем массив <tex>A</tex> для дальнейшего прорежения.

[[File:Fibonacci-heap-consolidate-example-2.png|thumb|center|500px|Удаление мимимума и создание массива]]

* Начнем процесс протяжения с первого элемента {{---}} <tex>56</tex>. Его степень равна <tex>0</tex> поэтому запишем его адрес в нулевую ячейку массива.

[[File:Fibonacci-heap-consolidate-example-3.png|thumb|center|500px|Состояние массива после первой итерации]]

* Следующий элемент <tex>22</tex> тоже имеет степень <tex>0</tex>. Возникает конфликт, который решается подвешиванием к меньшему корню большего. То есть к <tex>22</tex> подвешиваем <tex>56</tex> и увеличиваем степень <tex>22</tex> на <tex>1</tex>. В итоге степень <tex>22</tex> равна <tex>1</tex>. Записываем адрес <tex>22</tex> по индексу <tex>1</tex> в массив.

[[File:Fibonacci-heap-consolidate-example-4.png.png|thumb|center|500px|Состояние после второй итерации]]

* Делаем тоже самое, что и на предыдущих итерациях, но теперь объединяем <tex>32</tex> и <tex>84</tex>

[[File:Fibonacci-heap-consolidate-example-5.png|thumb|center|500px|Состояние после четвертой итерации]]

* Теперь у нас два элемента со степенью <tex>1</tex> в корневом списке. Объединим их подвесив к меньшему корню {{---}} <tex>22</tex>, больший {{---}} <tex>32</tex>. Теперь степень <tex>22</tex> равна <tex>2</tex>, запишем на <tex>2</tex> позицию массива обновленное значение.

[[File:Fibonacci-heap-consolidate-example-6.png|thumb|center|500px|Состояние после пятой итерации]]

* Ну и наконец аналогично объедений последние два элемента.

[[File:Fibonacci-heap-consolidate-example-7.png|thumb|center|500px|Финальное состояние кучи]]

==== Уменьшение значения элемента ====
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой [[Список |список]]. Итак, сам алгоритм:

# Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.
# Иначе, вырезаем дерево с текущей вершиной в корневой [[Список |список]], и производим каскадное вырезание родителя.
<code style="display:inline-block">
'''function''' decreaseKey(x: '''Node''', newValue: '''int'''):
'''if''' newValue > x.parent.key // если после изменения структкра дерева сохранится, то меняем и выходим
x.key = newValue
'''return'''
'''Node''' parent = x.parent // иначе вызываем cut и cascadingCut
cut(x)
cascadingCut(x.parent)
</code>
===== Вырезание =====
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree </tex>) и снимаем пометку с текущей вершины (<tex> x.mark = false </tex>).
<code style="display:inline-block">
'''function''' cut(x: '''Node''')
'''Node''' L = x.left
'''Node''' R = x.right
R.left = L // аккуратно удаляем текущую вершину
L.right = R
x.right = x
x.left = x
x.parent.degree--
'''if''' x.parent.child = x // чтобы родитель не потерял ссылку на сыновей проверяем: 
'''if''' x.right = x. // если узел который мы вырезаем содержится в родителе, то меняем его на соседний
x.parent.child <tex>= \varnothing</tex> // иначе у родителя больше нет детей
'''else'''
x.parent.child = x.right
x.parent <tex>= \varnothing</tex>
unionLists(min, x) // вставляем наше поддерево в корневой список
</code>

===== Каскадное вырезание =====
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (<tex> x.mark = false </tex>), то мы помечаем эту вершину (<tex> x.mark = true </tex>) и прекращаем выполнение операции. В противном случае применяем операцию <tex>\mathrm {cut}</tex> для текущей вершины и запускаем каскадное вырезание от родителя.
[[File:Каскадное вырезание.png|thumb|500px|Пример каскадного вырезания]]
<code style="display:inline-block">
'''function''' cascadingCut(x: '''Node''')
'''while''' x.mark = '''true''' // пока у нас помеченые вершины вырезаем их
cut(x)
x = x.parent
x.mark = true // последнюю вершину нужно пометить {{---}} у нее удаляли ребенка
</code>

'''Пример'''

Рисунок иллюстрирует пример каскадного вырезания:

* Изначально, куча состояла из <tex>3</tex> фибоначчиевых деревьев. У вершины с ключом <tex>24</tex> отсутствует <tex>1</tex> ребенок.
* Уменьшаем ключ <tex>26</tex> до <tex>5</tex> и делаем операцию <tex>\mathrm {cut}</tex> этого дерева. Получаем кучу с <tex>4</tex> деревьями и новым минимумом. Но у вершины с ключом <tex>24</tex> был удален второй ребенок, поэтому запускам операцию <tex>\mathrm {cascadingCut}</tex> для этой вершины: вырезаем ее, помещаем в корневой [[Список |список]] и помечаем ее родителя.
* У вершины с ключом <tex>7</tex> удален лишь один ребенок, поэтому операция <tex>\mathrm {cascadingCut}</tex> от нее не запускается. В итоге, получаем кучу, состоящую из <tex>5</tex> фибоначчиевых деревьев.

==== Удаление элемента ====
Удаление вершины реализуется через уменьшение ее ключа до <tex> -\infty </tex> и последующим извлечением минимума.
<code style="display:inline-block">
'''function''' delete(x: '''Node''')
decreaseKey(x, <tex>-\infty</tex>)
deleteMin()
</code>

== Время работы ==
==== Потенциал ====
Для анализа производительности операций введем потенциал для фибоначчиевой кучи как <tex> \Phi = trees + 2 * marked </tex>, где <tex> trees </tex> {{---}} количество элементов в корневом списке кучи, а <tex> marked </tex> {{---}} количество вершин, у которых удален один ребенок (то есть вершин с пометкой <tex> x.mark = true </tex>). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы.
==== Cоздание кучи ====
Очевидно, что реальное время работы {{---}} <tex> O(1) </tex>.
==== Вставка элемента ====
Для оценки амортизированной стоимости операции рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> trees(H') = trees(H) + 1 </tex> и <tex> marked(H') = marked(H) </tex>. Следовательно, увеличение потенциала составляет <tex> (trees(H) + 1 + 2 * marked(H)) - (trees(H) + 2 * marked(H)) = 1 </tex>. Так как реальное время работы составляет <tex> O(1) </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.
==== Получение минимального элемента ====
Истинное время работы {{---}} <tex> O(1) </tex>.
==== Соедининение двух куч ====
Реальное время работы {{---}} <tex> O(1) </tex>. Амортизированное время работы также <tex> O(1) </tex>, поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, <tex> \Phi_{n + 1} - \Phi_n = 0 </tex>.
==== Удаление минимального элемента====
Для доказательства времени работы этого алгоритма нам понадобится доказать несколько вспомогательных утверждений.
{{Лемма
|id=Лемма1
|statement=Для всех целых <tex> n \geqslant 2</tex>
<tex> F_n = 1 + \sum\limits_{i=0}^{n-2} F_i </tex>,
где <tex> F_n </tex> {{---}} <tex> n </tex>-ое число Фибоначчи, определяемое формулой:
<tex>
F_n =
\begin{cases}
0, & n = 0 \\
1, & n = 1 \\
F_{n-1} + F_{n-2}, & n \geqslant 2
\end{cases} </tex>
|proof=
Докажем лемму по индукции:

при <tex>n = 2</tex>

<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.

По индукции предполагаем, что <tex>F_{n-1} = 1 + \sum\limits_{i=0}^{n-3} F_i </tex>. Тогда

<tex>F_n = F_{n-1} + F_{n-2} = 1 + \sum\limits_{i=0}^{n-3} F_i + F_{n-2} = 1 + \sum\limits_{i=0}^{n-2} F_i</tex>
}}

{{Лемма
|id=Лемма2
|statement= Фибоначчиево дерево порядка <tex>n</tex> содержит не менее <tex>F_n</tex> вершин.
|proof=
Докажем это утверждение по индукции.
Пусть <tex>s_n</tex> {{---}} минимальный размер фибоначчиева дерева порядка <tex>n</tex>.

При <tex>n = 0</tex>

<tex>s_0 = 1 > F_0</tex>.

При <tex>n = 1</tex>

<tex>s_1 = 1 = F_1</tex>.

Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.
Пусть в нашем дереве удалено поддерево порядка <tex>n - 1</tex>. Тогда

<tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex>

Но по предыдущей [[#Лемма1|лемме]] :

<tex>1 + \sum\limits_{i=0}^{n-2} F_i = F_n</tex>. Следовательно, <tex>s_n \geqslant F_n</tex>
}}
{{Лемма
|id=Лемма3
|statement= <tex>F_n =O(\varphi^n)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex>
|proof=
Для начала докажем, что <tex>F_n =</tex> <tex dpi="160">\frac {\varphi^n - (-\varphi)^{-n}} {\sqrt 5}</tex>

Используем для этого математическую индукцию.

При <tex>n = 0</tex>

<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.

При <tex>n = 1</tex>

<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {1} {\sqrt 5}(\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}) = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.

По индукции предполагаем, что <tex>F_{n-1} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5}</tex> и <tex>F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5}</tex>. Тогда

<tex>F_n = F_{n-1} + F_{n-2} =</tex> <tex dpi="160">\frac {\varphi^{n-1} - (-\varphi)^{1-n}} {\sqrt 5} + \frac {\varphi^{n-2} - (-\varphi)^{2-n}} {\sqrt 5} =</tex>

<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n-1} - (-\varphi)^{1-n} + \varphi^{n-2} - (-\varphi)^{2-n}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{n}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-n}(-\varphi + \varphi^{2}))</tex>

Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex>

Поскольку <tex>\left\vert (-\varphi)^{-1} \right\vert < 1</tex>, то выполняются неравенства <tex dpi="160">\frac {(-\varphi)^{-n}} {\sqrt 5} < \frac {1} {\sqrt 5} < \frac {1} {2}</tex>. Таким образом, <tex>n</tex>-ое число Фибоначчи равно <tex dpi="160">\frac {\varphi^{n}} {\sqrt 5}</tex>, округленному до ближайшего целого числа. Следовательно, <tex>F_n =O(\varphi^n)</tex>.
}}

{{Лемма
|id=Лемма4
|statement=Максимальная степень <tex>degree</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(\log n)</tex>
|proof=
Пусть <tex>x</tex> {{---}} произвольная вершина в фибоначчиевой куче с <tex>n</tex> вершинами, и пусть <tex>k</tex> {{---}} степень вершины <tex>x</tex>. Тогда по [[#Лемма2|доказанному выше]] в дереве, корень которого <tex>x</tex>, содержится не менее <tex>F_k</tex> вершин, что в свою очередь по [[#Лемма3|лемме]] равно <tex>O(\varphi^k)</tex>.
То есть

<tex>n \geqslant \varphi^{k}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant k</tex>

Таким образом, максимальная степень <tex>degree</tex> произвольной вершины равна <tex>O(\log n)</tex>.
}}

Итоговая асимптотика операции <tex>\mathrm {extraxtMin}</tex>, учитывая и вспомогательную функцию <tex> \mathrm {consolidate} </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(degree)+O(degree)=O(degree) </tex>. По доказанной выше [[#Лемма4|лемме]] <tex>O(degree) = O(\log(n))</tex>.

Учетная стоимость <tex> \mathrm {consolidate} </tex> равна <tex> O(degree) </tex>. Докажем это:

Изначально в корневом списке было не более <tex> degree + trees - 1 </tex> вершин, поскольку он состоит из исходного списка корней с <tex>trees</tex> узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает <tex> degree </tex>. В ходе операции <tex> \mathrm {consolidate} </tex> мы сделали <tex> O(degree + trees) </tex> слияний деревьев. Потенциал перед извлечением минимума равен <tex> trees + 2 * marked </tex>, а после не превышает <tex> degree + 1 + 2 * marked</tex>, поскольку в корневом списке остается не более <tex> degree + 1 </tex> узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит

<tex> O(degree + trees) + (degree + 1 + 2 * marked) - (trees + 2 * marked) = O(degree) + O(trees) - trees</tex>

Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка {{---}} <tex> O(degree) </tex>
==== Уменьшение значения элемента ====
Докажем, что амортизированное время работы операции <tex> \mathrm {decreaseKey} </tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Пусть мы вызвали процедуру каскадного вырезания подверглось <tex> k </tex> раз. Так как реальное время работы каждой итерации <tex> \mathrm {cascadingCut} </tex> составляет <tex> O(1) </tex>, то реальное время работы операции <tex> \mathrm {decreaseKey} </tex> {{---}} <tex> O(k) </tex>.

Рассмотрим, как изменится потенциал в результате выполнения данной операции. Пусть <tex> H </tex> {{---}} фибоначчиева куча до вызова <tex> \mathrm {decreaseKey} </tex>. Тогда после <tex> k </tex> итераций операции <tex> \mathrm {cascadingCut} </tex> вершин с пометкой <tex> x.mark = true </tex> стало как минимум на <tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, уменьшает количество помеченных вершин на одну, и в результате последнего вызова одну вершину мы можем пометить. В корневом списке прибавилось <tex> k </tex> новых деревьев (<tex> k - 1 </tex> дерево за счет каскадного вырезания и еще одно из-за самого первого вызова операции <tex> \mathrm {cut} </tex>).

В итоге, изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((trees + k) + 2 * (marked + k - 2)) - (trees + 2 * marked) = 4 - k </tex>. Следовательно, амортизированная стоимость не превышает <tex> O(k) + 4 - k </tex>. Но поскольку мы можем соответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> \mathrm {decreaseKey} </tex> равна <tex> O(1) </tex>.
==== Удаление элемента ====
Амортизированное время работы: <tex> O(1) + O(degree) = O(degree) </tex>.

Поскольку ранее мы показали, что <tex> degree = O(\log n ) </tex>, то соответствующие оценки доказаны.
==== Итоговая таблица ====
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Операция
!style="background-color:#EEE"| Амортизированная сложность
|-align="center"
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {makeHeap}</tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex>
|-align="center"
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {insert}</tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex>
|-align="center"
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {getMin}</tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex>
|-align="center"
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {merge}</tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex>
|-align="center"
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {extractMin}</tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex>
|-align="center"
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {decreaseKey}</tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>O(1)</tex>
|-align="center"
|style="background-color:#FFF;padding:2px 10px"| <tex>\mathrm {delete}</tex>
|style="background-color:#FFF;padding:2px 10px"| <tex>O(\log n )</tex>
|}

== Недостатки и достоинства ==
'''Недостатки''':
* Большое потребление памяти на узел(минимум 21 байт)
* Большая константа времени работы, что делает ее малоприменимой для реальных задач
* Некоторые операции в худшем случае могут работать за <tex>O(n)</tex> времени
'''Достоинства''':
* Одно из лучших асимптотических времен работы для всех операций

== См. также ==
* [[Приоритетные очереди]]
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Левосторонняя куча]]
* [[Тонкая куча]]
* [[Толстая куча на избыточном счетчике]]
* [[Куча Бродала-Окасаки]]
== Примечания ==
<references/>
== Источники информации ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4
* [[wikipedia:en:Числа Фибоначчи|Числа Фибоначчи {{---}} Википедия]]
* [[wikipedia:en:Fibonacci heap|Фибоначчиева куча {{---}} Википедия]]
* [https://www.cs.usfca.edu/~galles/visualization/FibonacciHeap.html Fibonacci heap visualization]
* [http://www.intuit.ru/department/algorithms/dscm/7/2.html Фибоначчиевы кучи — INTUIT.ru]
* [http://www.cs.duke.edu/courses/fall05/cps230/L-11.pdf Fibonacci Heaps {{---}} Duke University]
* [https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf Fibonacci Heaps {{---}} Princeton University]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Приоритетные очереди]]

Быстрая сортировка

2018-04-03T18:12:44Z

188.130.155.157: /* Нерекурсивная реализация быстрой сортировки */ {{mxt|l}} перепутали с {{mxt|1}}

'''Быстрая сортировка''' (англ. ''quick sort'', сортировка Хоара) {{---}} один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы <Tex>O(n\log{n})</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из <tex>n</tex> элементов в худшем случае может составить <tex>\Theta(n^2)</tex>, на практике этот алгоритм является одним из самых быстрых.

==Алгоритм==
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй".
* Массив <tex> a[l \ldots r]</tex> типа <tex> T </tex> разбивается на два (возможно пустых) подмассива <tex> a[l \ldots q]</tex> и <tex> a[q+1 \ldots r]</tex>, таких, что каждый элемент <tex> a[l \ldots q]</tex> меньше или равен <tex> a[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> a[q+1 \ldots r]</tex>. Индекс вычисляется в ходе процедуры разбиения.
* Подмассивы <tex> a[l \ldots q]</tex> и <tex> a[q+1 \ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
* Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив <tex> a[l \ldots r]</tex> оказывается отсортированным.

==Псевдокод==
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
'''if''' l < r
'''int''' q = partition(a, l, r)
quicksort(a, l, q)
quicksort(a, q + 1, r)
Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(a, 0, length[a] - 1)}</tex>.

===Разбиение массива===
Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> типа <tex> T </tex> нужным образом.
Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент
<tex> a[(l + r) / 2] </tex>. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.

Переменная <tex> v </tex> сохраняет значение разделяющего элемента <tex> a[(l + r) / 2] </tex>, a <tex> i </tex> и <tex> j </tex> представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение <tex> i </tex> и уменьшает значение <tex> j </tex> на <tex> 1 </tex>, причем условие, что ни один элемент слева от <tex> i </tex> не больше <tex> v </tex> и ни один элемент справа от <tex> j </tex> не меньше <tex> v </tex>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается.

'''int''' partition(a: '''T'''[n], '''int''' l, '''int''' r)
'''T''' v = a[(l + r) / 2]
'''int''' i = l
'''int''' j = r
'''while''' (i <tex> \leqslant </tex> j)
'''while''' (a[i] < v)
i++
'''while''' (a[j] > v)
j--
'''if''' (i <tex> \geqslant </tex> j)
'''break'''
swap(a[i++], a[j--])
'''return''' j

==Асимптотика==
===Худшее время работы===
Предположим, что мы разбиваем массив так, что одна часть содержит <tex>n - 1</tex> элементов, а вторая {{---}} <tex>1</tex>. Поскольку процедура разбиения занимает время <tex>\Theta(n)</tex>, для времени работы <tex>T(n)</tex> получаем соотношение:

<tex>T(n) = T(n - 1) + \Theta(n) = \sum\limits_{k=1}^{n} \Theta(k) = \Theta(\sum\limits_{k=1}^{n} k) = \Theta(n^2)</tex>.

Мы видим, что при максимально несбалансированном разбиении время работы составляет <tex>\Theta(n^2)</tex>. В частности, это происходит, если массив изначально отсортирован.

===Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного===
В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает <tex>\Theta(n^2)</tex> сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться <tex>1</tex>, а в другом <tex> n - 1 </tex> элемент).

Заполним сначала массив <tex>a</tex> длины <tex>n</tex> элементами от <tex>1</tex> до <tex> n </tex>, затем применим следующий алгоритм (нумерация с нуля):

'''void''' antiQsort(a: '''T'''[n])
'''for''' i = 0 '''to''' n - 1
swap(a[i], a[i / 2])
Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.

При выполнении <tex>\mathrm{partition}</tex> делается <tex>\Theta(n)</tex> сравнений из-за того, что с помощью индексов <tex>i</tex> и <tex>j</tex> мы проходим в лучшем случае <tex>\Omega(n)</tex> элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае <tex>O(2n)</tex> элементов (если оба индекса полностью проходят массив). При каждом изменении индекса делается сравнение, значит, процедура <tex>\mathrm{partition}</tex> делает <tex>\Theta(n)</tex> сравнений с точностью до константы.

Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. <tex>\mathrm{antiQsort}</tex> на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А <tex>\mathrm{partition}</tex> делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как <tex> \mathrm{antiQsort} </tex> на массиве любой длины будет выполнять операции, обратные <tex>\mathrm{partition}</tex>. Фактически, <tex>\mathrm{partition}</tex> {{---}} это <tex>\mathrm{antiQsort}</tex>, запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала <tex>i</tex> дойдет до середины массива, до опорного элемента, <tex>j</tex> останется равным индексу последнего элемента. Затем произойдет <tex>\mathrm{swap}</tex> и <tex>i</tex> снова начнет увеличиваться, пока не дойдет до последнего элемента, <tex>j</tex> опять не изменит свою позицию. Потом произойдет выход из <tex>\mathrm{while}</tex>.

Разбиение массива будет произведено <tex>\Theta(n)</tex> раз, потому что разбиение производится на массивы длины <tex>1</tex> и <tex> n - 1 </tex> из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше). Следовательно, на массиве, который строится описанным выше способом, выполняется <tex>\Theta(n)</tex> <tex>\mathrm{partition}</tex> и <tex>\Theta(n)</tex> сравнений для каждого выполнения <tex>\mathrm{partition}</tex>. Тогда быстрая сортировка выполнит <tex>\Theta(n^2)</tex> сравнений для массива, построенного таким способом.

===Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента===

Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае {{---}} <tex>\Theta(n^2)</tex>) количество сравнений. Такое число сравнений достигается при разбиении на массивы длиной <tex>1</tex> и <tex>n-1</tex> на каждой итерации.
Создадим массив <tex>a</tex> длины <tex>n</tex>, заполненный элементами типа <tex>pair</tex>. Такой элемент хранит пару значений <tex>(val, key)</tex>, где <tex>val</tex> {{---}} элемент массива, а <tex>key</tex> {{---}} индекс. Изначально <tex>a[i]</tex> элемент имеет вид <tex>(0, i)</tex>.

Далее, запустим для данного массива алгоритм быстрой сортировки. Сравниваем два элемента типа <tex>pair</tex> по их значениям <tex>val</tex>. На каждом шаге будем выполнять следующие действия: при обращении к <tex>i</tex>-ому элементу в качестве опорного на шаге под номером <tex>k</tex>, присвоим <tex>val = n-k+1</tex> для элемента <tex>a[i]</tex>. Затем выполним шаг сортировки. После завершения работы алгоритма быстрой сортировки, дополнительно отсортируем получившиеся элементы <tex>pair</tex> по значениям <tex>key</tex>. Искомым будет являться массив элементов <tex>val</tex> в соответствующей последовательности.

Пример для <tex>n = 4</tex>, при последовательном выборе опорных элементов <tex>2, 2, 1, 1</tex>.

<center>

{| class="wikitable"
!colspan="8"| Построение массива

|-

! Шаг 1.0 || Шаг 1.1 || Шаг 1.2 || Шаг 2.0 || Шаг 2.1 || Шаг 2.2 || Шаг 3.0
|-align="right"
|style="text-align: center;"|1 2 3 4 0 '''0''' 0 0
| style="text-align: center;"|1 2 3 4 0 '''4''' 0 0
|style="text-align: center;"|1 4 3 2 0 0 0 '''4'''
|style="text-align: center;"|1 4 3 2 0 '''0''' 0 4
|style="text-align: center;"|1 4 3 2 0 '''3''' 0 4
|style="text-align: center;"|1 3 4 2 0 0 '''3''' 4
|style="text-align: center;"|1 3 4 2 '''0''' 0 3 4
|-
! Шаг 3.1 || Шаг 3.2 || Шаг 4.0 || Шаг 4.1 || Шаг 4.2 || colspan="2" style="vertical-align: middle;"| Результат

|-align="right"
|style="text-align: center;"|1 3 4 2 '''2''' 0 3 4
|style="text-align: center;"|3 1 4 2 0 '''2''' 3 4
|style="text-align: center;"|3 1 4 2 '''0''' 2 3 4
|style="text-align: center;"|3 1 4 2 '''1''' 2 3 4
|style="text-align: center;"|3 1 4 2 '''1''' 2 3 4
| colspan="2" style="text-align: center;vertical-align: middle;" |'''1 2 3 4''' '''2 4 1 3'''

|-

!colspan="8" | Итоговый массив
|-
|align="center" colspan="8"|
2 4 1 3
|}
</center>

Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу минимальное значение. Следовательно, при выполнении <tex>\mathrm{quicksort}</tex> алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента).
Таким образом, так как каждый раз массив разбивается на две части {{---}} большие или равные опорному элементы и меньшие его {{---}} на каждом шаге имеем разбиение на массивы длины <tex>1</tex> и <tex>n-1</tex>, чего мы, собственно, и добивались. При таком выполнении алгоритма происходит <tex>\Theta(n^2)</tex> разделений на два подмассива, и на каждом разделении выполняется <tex>\Theta(n^2)</tex> сравнений.
Следовательно, на данном массиве быстрая сортировка работает за <tex>\Theta(n^2)</tex>.

===Среднее время работы===
{{
Лемма
|statement=Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.
|proof=Пусть <tex>X</tex> {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1 \ldots z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1} \ldots z_j\}</tex>.

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

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

<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex> если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex> и <tex>X_{ij} = 0</tex>, если сравнения не произошло.

Применим к обоим частям равенства операцию вычисления матожидания и воспользовавшись ее линейностью получим

<tex>E[X] = E\left[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}\right] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} E[X_{ij}] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex>

Осталось вычислить величину <tex>Pr\{z_i</tex> сравнивается с <tex>z_j\}</tex> {{---}} вероятность того, что <tex>z_i</tex> сравнивается с <tex>z_j</tex>. Поскольку предполагается, что все элементы в массиве различны, то при выборе <tex>x</tex> в качестве опорного элемента впоследствии не будут сравниваться никакие <tex>z_i</tex> и <tex>z_j</tex> для которых <tex>z_i < x < z_j</tex>. С другой стороны, если <tex>z_i</tex> выбран в качестве опорного, то он будет сравниваться с каждым элементом <tex>Z_{ij}</tex> кроме себя самого. Таким образом элементы <tex>z_i</tex> и <tex>z_j</tex> сравниваются тогда и только тогда когда первым в множестве <tex>Z_{ij}</tex> опорным элементом был выбран один из них.

<tex>Pr\{z_i</tex> сравнивается с <tex>z_j\} =
Pr\{</tex>первым опорным элементом был <tex>z_i</tex> или <tex>z_j\} =
Pr\{</tex>первым опорным элементом был <tex>z_i\} +
Pr\{</tex>первым опорным элементом был <tex>z_j\} = </tex>
<tex> =\dfrac {1}{j-i+1} + \dfrac {1}{j-i+1} = \dfrac {2}{j-i+1} </tex>

<tex> E[X] = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} \dfrac {2}{j-i+1} = \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \dfrac 2{k+1} < \sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^{n-i} \dfrac 2{k} </tex> <tex>= \sum\limits_{i=1}^{n-1}O(\log n) = O(n \log n) </tex>
}}
Mатожидание времени работы быстрой сортировки будет <tex>O(n \log n)</tex>.

==Модификации==

===Нерекурсивная реализация быстрой сортировки===
Для выполнения быстрой сортировки можно воспользоваться [[Стек | стеком]], в котором в виде сортируемых подмассивов содержится перечень действий, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подмассива, он выталкивается из стека. После разделения массива получаются два подмассива, требующих дальнейшей обработки, которые и заталкиваются в стек.
Представленная ниже нерекурсивная реализация использует стек, заменяя рекурсивные вызовы помещением в стек параметров функции, а вызовы процедур и выходы из них — циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. Мы помещаем больший из двух подмассивов в стек первым с тем, чтобы максимальная глубина стека при сортировке <tex>N</tex> элементов не превосходила величины <tex>\log n</tex>.
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
'''stack'''< '''pair'''<'''int''','''int'''> > s
s.push(l, r)
'''while''' (s.isNotEmpty)
(l, r) = s.pop()
'''if''' (r <tex> \leqslant </tex> l)
'''continue'''
'''int''' i = partition(a, l, r)
'''if''' (i - l > r - i)
s.push(l, i - 1)
s.push(i + 1, r)
'''else'''
s.push(i + 1, r)
s.push(l, i - 1)

В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <tex>\log n</tex>, а в худшем случае вырожденного разделения она вообще будет не более <tex> n </tex> — вся обработка пройдёт в цикле первого уровня рекурсии.

===Улучшенная быстрая сортировка===

Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может
привести к существенному повышению эффективности быстрой сортировки. Функция <tex>\mathrm{median}</tex> возвращает индекс элемента, являющегося медианой трех элементов. После этого он и средний элемент массива меняются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной <tex> M = 11</tex> и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется [[Сортировка вставками | сортировка вставками]].

'''const int''' M = 10
'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
'''if''' (r - l <tex> \leqslant </tex> M)
insertion(a, l, r)
'''return'''
'''int''' med = median(a[l], a[(l + r) / 2], a[r])
swap(a[med], a[(l + r) / 2])
'''int''' i = partition(a, l, r)
quicksort(a, l, i)
quicksort(a, i + 1, r)

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

===Быстрая сортировка с разделением на три части===

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

В основу программы положено разделение массива на три части:
на элементы,меньшие разделяющего элемента <tex> a[l] \ldots a[i]</tex>,
элементы, равные разделяющему элементу <tex>a[i+1] \ldots a[j-1]</tex>,
и элементы большие разделяющего элемента <tex>a[j] \ldots a[r]</tex>.
После этого сортировка завершается двумя рекурсивными вызовами.

[[Файл:G3.png |400px|thumb|center| Разделение массива <tex> a </tex>]]

Элементы массива равные разделяющему элементу находятся между <tex> l </tex> и <tex> p </tex> и между <tex> q </tex> и <tex> r </tex>. В разделяющем цикле, когда указатели просмотра перестают изменяться и выполняется обмен значениями <tex> i </tex> и <tex> j </tex>, каждый из этих элементов проверяется на предмет равенства разделяющему элементу. Если элемент, который сейчас находится слева, равен разделяющему элементу, то при помощи операции обмена он помещается в левую часть массива, если элемент, который сейчас находится справа, равен разделяющему элементу, то в результате операции обмена он помещается в правую часть массива.
После того как указатели пересекутся, элементы, равные разделяющему элементу и находящиеся на разных концах массива, после операции обмена попадают в свои
окончательные позиции. После этого указанные ключи могут быть исключены из подмассивов, для которых выполняются последующие рекурсивные вызовы.

'''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)
'''T''' v = a[r]
'''if''' (r <tex> \leqslant </tex> l)
'''return'''
'''int''' i = l
'''int''' j = r - 1
'''int''' p = l - 1
'''int''' q = r
'''while''' ''(i <tex> \leqslant </tex> j)''
'''while''' (a[i] < v)
i++
'''while''' (a[j] > v)
j--
'''if''' (i <tex> \geqslant </tex> j)
'''break'''
swap(a[i], a[j])
'''if''' (a[i] == v)
p++
swap(a[p], a[i])
i++
'''if''' (a[j] == v)
q--
swap(a[q], a[j])
j--
swap(a[i], a[r])
j = i - 1
i++
'''for''' ('''int''' k = l; k <tex> \leqslant </tex> p; k++, j--)
swap(a[k], a[j])
'''for''' ('''int''' k = r - 1; k <tex> \geqslant </tex> q; k--, i++)
swap(a[k], a[i])
quicksort(a, l, j)
quicksort(a, i, r)

===Параллельная сортировка===

Еще одной оптимизацией является [[PSRS-сортировка|параллельная сортировка]] на основе быстрой.
Пусть, исходный набор данных расположен на первом процессоре, с него начинается работа алгоритма. Затем исходный массив окажется разделенным на две части, меньшая из которых передастся другому свободному процессору, большая останется на исходном для дальнейшей обработки. Далее обе части опять будут разделены и опять на двух исходных останутся большие части, а меньшие отправятся другим процессорам. В этом заключается ускорение алгоритма. При задействовании всех процессоров, все части параллельно будут сортироваться последовательным алгоритмом.

===Introsort===

Для предотвращения ухудшения времени работы быстрой сортировки до <tex>O(n^2)</tex> при неудачных входных данных, также можно использовать алгоритм сортировки Introsort.
Он использует быструю сортировку и переключается на [[Сортировка кучей|пирамидальную сортировку]], когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Так как после нескольких итераций быстрой сортировки с применением разных эвристик массив с большей вероятностью окажется «почти отсортированным», то пирамидальная сортировка может довольно быстро закончить дело. Также, пирамидальная сортировка хороша тем, что требует <tex>O(1)</tex> дополнительной памяти, в отличие от, например, сортировки слиянием, где потребуется <tex>O(n)</tex> дополнительной памяти.

==См. также==
* [[Сортировка Шелла]]
* [[Сортировка кучей]]
* [[Сортировка слиянием]]
* [[Timsort]]
* [[Smoothsort]]
* [[PSRS-сортировка]]

== Источники информации ==
* [[wikipedia:ru:Быстрая сортировка|Википедия {{---}} Быстрая сортировка]]
* [[wikipedia:en:Quicksort|Wikipedia {{---}} Quicksort]]
* [[wikipedia:en:Introsort|Wikipedia {{---}} Introsort]]
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ глава 7
* ''Р. Седжвик'': Фундаментальные алгоритмы на С++ части 1 - 4

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]
[[Категория: Сортировки на сравнениях]]