Изменения
Нет описания правки
'''Блинная сортировка''' (англ. ''pancake sorting'') {{---}} алгоритм [[Сортировки | сортировки]] с помощью одной операции {{---}} переворота элементов последовательности до какого-то индекса (префикса последовательности). Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.
== Корректность ==
Для начала покажем, что любую последовательность можно отсортировать с помощью блинной сортировки. Для этого будет предложен алгоритм, позволяющий отсортировать любой массив, сделав не более <tex>2n</tex> операций, где <tex>n</tex> {{---}} размер массива.
Найдём максимальный элемент последовательности с номером <tex>i</tex> и развернём префикс массива до <tex>i</tex>-го элемента. Теперь максимальный элемент находится в начале массива. Развернём весь массив, теперь максимальный элемент находится в конце массива. Сделаем то же самое рекуррентно для префикса длины <tex>n-1</tex>. Переместим второй по возрастанию элемент в конец подотрезка, после чего последние два элемента будут отсортированы, и продолжим для префикса длины <tex>n-2</tex>. Таким образом, на каждой итерации мы сделаем две операции, и всего итераций будет не больше <tex>n</tex> (их может быть меньше <tex>n</tex>: если после <tex>i</tex>-ой итерации отсортированным окажется суффикс длины больше, чем <tex>i+1</tex>, можно рекурсивно запустить алгоритм на префиксе длины <tex>n-i-k</tex> вместо <tex>n-i-1</tex>). Тогда суммарное количество операций не превосходит <tex>2n</tex> и любая последовательность может быть отсортирована таким образом.
== Оценки на количество операций ==
Существуют простые оценки: <tex>2n</tex> сверху и, для <tex>n \geqslant 4</tex>, <tex>n</tex> снизу. Более сложные границы были предложены в 1978 году Биллом Гейтсом и Христосом Пападимитриу, и улучшить их получилось лишь в 2008.
=== Наивные ===
==== Верхняя ====
Оценка в <tex>2n</tex> операций следует из доказательства корректности алгоритма, в котором предлагается алгоритм сортировки любой последовательности за <tex>2n</tex> операций. Она может быть улучшена до <tex>2n-3</tex> чуть более умной сортировкой последних элементов.
==== Нижняя ====
Назовём ''соседством'' в массиве пару элементов, которые идут последовательно в массиве и для которых нет элемента, большего одного из них и меньшего другого. Если максимальный элемент находится в конце массива, это тоже будет считаться соседством (будем считать, что массив сортируется по возрастанию).
Для любого <tex>n\geqslant 4</tex> существует массив, в котором нет соседств. С другой стороны, отсортированный массив имеет <tex>n</tex> соседств, и за один переворот можно добавить не больше одного соседства, поэтому отсортировать массив, сделав меньше, чем <tex>n</tex> переворотов, невозможно.
=== Продвинутые ===
Для начала введём некоторые обозначения.
Пусть <tex>S_n</tex> {{---}} множество перестановок элементов массива длины <tex>n</tex>. Будем считать перестановки строками в <tex>\Sigma^*_n</tex>, где <tex>\Sigma_n=\{1, 2, \ldots, n\}</tex>. Введём [[Бинарное отношение | бинарное отношение]] <tex>R: \Sigma^*_n \rightarrow \Sigma^*_n</tex>: <tex>\pi R\sigma</tex> тогда и только тогда, когда <tex>\pi =xy</tex> и <tex>\sigma =x^Ry</tex>, где <tex>\pi, \sigma \in \Sigma^*_n</tex> и <tex>x^R</tex> обозначает развёрнутую <tex>x</tex>.
Пусть <tex>\pi</tex> {{---}} перестановка, тогда <tex>f(\pi)</tex> {{---}} наименьшее <tex>k</tex> такое, что существует последовательность перестановок <tex>\pi_0 R \pi_1 R \ldots R \pi_k = e_n</tex>, где <tex>e_n = 123\ldots n</tex>. Тогда для числа <tex>n</tex> будем обозначать <tex>f(n)</tex> за максимальное <tex>f(\pi)</tex> среди всех <tex>\pi \in S_n</tex>.
Пусть <tex>\pi</tex> {{---}} перестановка из <tex>S_n</tex>. Тогда <tex>\pi (j)</tex> {{---}} число номер <tex>j</tex> в перестановке для <tex>1 \leqslant j \leqslant n</tex>. Соседством в <tex>\pi</tex> назовём пару <tex>(j, j+1)</tex> такую, что <tex>|\pi (j) - \pi (j+1)| = 1</tex>. Также будем называть соседством пару <tex>(j, j+1)</tex>, если <tex>\{\pi (j), \pi (j+1) \} = \{1, n\}</tex>. Для <tex>x \in \Sigma^*_n</tex> будем обозначать длину <tex>x</tex> как <tex>|x|</tex>.
Пусть <tex>\pi=xby</tex>, <tex>x, b, y \in \Sigma^*_n</tex>. <tex>b</tex> будем называть ''блоком'', если для любого <tex>j</tex> такого, что <tex>|x|+1 \leqslant j \leqslant |x| + |b| - 1</tex>, пара <tex>(j, j+1)</tex> {{---}} соседство, при этом пары <tex>(|x|, |x|+1)</tex> и <tex>(|x|+|b|-1, |x|+|b|</tex> не являются соседствами. Если <tex>\pi (j)</tex> не является частью блока, то есть <tex>(j-1, j)</tex> и <tex>(j, j+1)</tex> {{---}} не соседства, элемент <tex>\pi (j)</tex> будем называть ''свободным''.
За <tex>o</tex> будем обозначать элемент из <tex>\{-1, 1\}</tex>. Подразумевается, что сложение проводится по модулю <tex>n</tex>.
==== Верхняя ====
Будет предложен алгоритм, который изменит перестановку <tex>\pi</tex> так, чтобы в ней было <tex>n-1</tex> соседств. После этого отсортировать массив можно не более чем за 4 действия (в иллюстрациях дальше показана последовательность действий, состояние в следующей строке получается из состояния в предыдущей одним разворотом префикса):
{| border="1" style="border-collapse: collapse; float: left; margin-right: 30px;"
| colspan="2" style="text-align: center"| <tex>a</tex>
|-
| style="text-align: right" | <tex>k-1 \ldots 1</tex>
|<tex>n \ldots k</tex>
|-
| style="text-align: right" | <tex>k\ldots n</tex>
|<tex>1\ldots k-1</tex>
|-
| style="text-align: right" | <tex>n\ldots k</tex>
|<tex>1 \ldots k-1</tex>
|-
| style="text-align: right" | <tex>k-1 \ldots 1</tex>
|<tex>k \ldots n</tex>
|-
| style="text-align: right" | <tex>1 \ldots k-1</tex>
|<tex>k \ldots n</tex>
|}
{| border="1" style="border-collapse: collapse;"
| colspan="2" style="text-align: center" | <tex>b</tex>
|-
| style="text-align: right" | <tex>k\ldots n</tex>
|<tex>1\ldots k-1</tex>
|-
| style="text-align: right" | <tex>n\ldots k</tex>
|<tex>1\ldots k-1</tex>
|-
| style="text-align: right" | <tex>k-1 \ldots 1</tex>
|<tex>k\ldots n</tex>
|-
| style="text-align: right" | <tex>1\ldots k-1</tex>
|<tex>k\ldots n</tex>
|}
=== Алгоритм ===
'''Алгоритм''':
* '''входные данные''': перестановка <tex>\pi\in S_n</tex>
* '''выходные данные''': перестановка <tex>\sigma</tex> с <tex>n-1</tex> соседством
Циклически повторять следующее. Пусть <tex>t</tex> {{---}} первый элемент <tex>\pi</tex> (<tex>\pi = t\pi '</tex>). Как минимум одно из условий выполняется, выполнить соответствующее действие:
# <tex>t</tex> свободный, <tex>t+o</tex> свободный. Выполнить разворот <tex>a</tex>,
# <tex>t</tex> свободный, <tex>t+o</tex> {{---}} первый элемент блока. Выполнить разворот <tex>b</tex>,
# <tex>t</tex> свободный, и <tex>t+1</tex>, и <tex>t-1</tex> {{---}} последние элементы в блоке. Выполнить развороты <tex>c</tex>,
# <tex>t</tex> в блоке, <tex>t+o</tex> свободен. Выполнить разворот <tex>d</tex>,
# <tex>t</tex> в блоке, <tex>t+o</tex> {{---}} первый элемент блока. Выполнить разворот <tex>e</tex>,
# <tex>t</tex> в блоке с последним элементом <tex>t+k\cdot o</tex> (<tex>k>0</tex>), <tex>t-o</tex> {{---}} последний элемент другого блока, и <tex>t+(k+1)\cdot o</tex> свободен. Выполнить перевороты <tex>f</tex> или <tex>g</tex> в зависимости от расположения блоков,
# <tex>t</tex> в блоке с последним элементом <tex>t+k\cdot o</tex> (<tex>k>0</tex>), <tex>t-o</tex> {{---}} последний элемент другого блока, и <tex>t+(k+1)\cdot o</tex> в блоке. Выполнить развороты <tex>h</tex> или <tex>k</tex> в зависимости от того, в начале или в конце блока находится элемент <tex>t+(k+1)\cdot o</tex>,
# ничего из перечисленного выше. В перестановке <tex>\pi</tex> <tex>n-1</tex> соседство. Завершить работу алгоритма.
Необходимые развороты:
{| border="1" style="border-collapse: collapse; float: left; margin-right: 30px; text-align: center;"
| colspan="4" style="text-align: center"| <tex>a</tex>
|-
| <tex>t</tex>
| <tex>\ldots</tex>
| <tex>t+o</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>t</tex>
| <tex>t+o</tex>
| <tex>\ldots</tex>
|}
{| border="1" style="border-collapse: collapse; float: left; margin-right: 30px; text-align: center;"
| colspan="4" style="text-align: center"| <tex>b</tex>
|-
| <tex>t</tex>
| <tex>\ldots</tex>
| <tex>t+o\ldots</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>t</tex>
| <tex>t+o\ldots</tex>
| <tex>\ldots</tex>
|}
{| border="1" style="border-collapse: collapse; float: left; margin-right: 30px; text-align: center;"
| colspan="6" style="text-align: center"| <tex>c</tex>
|-
| <tex>t</tex>
| <tex>\ldots</tex>
| <tex>\ldots t+o</tex>
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>\ldots</tex>
|-
| <tex>t+o\ldots</tex>
| <tex>\ldots</tex>
| <tex>t</tex>
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>\ldots t+o</tex>
| <tex>t</tex>
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>\ldots</tex>
|-
| <tex>t-o \ldots</tex>
| <tex>\ldots</tex>
| <tex>t</tex>
| <tex>t+o \ldots</tex>
| <tex>\ldots</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>t</tex>
| <tex>t+o \ldots</tex>
| <tex>\ldots</tex>
| <tex>\ldots</tex>
|}
{| border="1" style="border-collapse: collapse; float: left; margin-right: 30px; text-align: center;"
| colspan="4" style="text-align: center"| <tex>d</tex>
|-
| <tex>t\ldots</tex>
| <tex>\ldots</tex>
| <tex>t+o</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>\ldots t</tex>
| <tex>t+o</tex>
| <tex>\ldots</tex>
|}
{| border="1" style="border-collapse: collapse; text-align: center;"
| colspan="4" style="text-align: center"| <tex>e</tex>
|-
| <tex>t\ldots</tex>
| <tex>\ldots</tex>
| <tex>t+o\ldots</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>\ldots t</tex>
| <tex>t+o \ldots</tex>
| <tex>\ldots</tex>
|}
{| border="1" style="border-collapse: collapse; float: left; margin-right: 30px; text-align: center;"
| colspan="6" style="text-align: center"| <tex>f</tex>
|-
| <tex>t\ldots t+ko</tex>
| <tex>\ldots</tex>
| <tex>t+(k+1)o</tex>
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>\ldots</tex>
|-
| <tex>t+(k+1)o</tex>
| <tex>\ldots</tex>
| <tex>t+ko\ldots t</tex>
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>t+(k+1)o</tex>
| <tex>t+ko\ldots t</tex>
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>\ldots</tex>
|-
| <tex>t-o \ldots</tex>
| <tex>\ldots</tex>
| <tex>t \ldots t+ko</tex>
| <tex>t+(k+1)o</tex>
| <tex>\ldots</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>t \ldots t+ko</tex>
| <tex>t+(k+1)o</tex>
| <tex>\ldots</tex>
| <tex>\ldots</tex>
|}
{| border="1" style="border-collapse: collapse; text-align: center;"
| colspan="6" style="text-align: center"| <tex>g</tex>
|-
| <tex>t \ldots t+ko</tex>
| <tex>\ldots</tex>
| <tex>\ldots t-o</tex>
| <tex>\ldots</tex>
| <tex>t+(k+1)o</tex>
| <tex>\ldots</tex>
|-
| <tex>t+(k+1)o</tex>
| <tex>\ldots</tex>
| <tex>t-o \ldots</tex>
| <tex>\ldots</tex>
| <tex>t+ko \ldots t</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>\ldots to</tex>
| <tex>\ldots</tex>
| <tex>t+(k+1)o</tex>
| <tex>t+ko \ldots t</tex>
| <tex>\ldots</tex>
|-
| <tex>t \ldots t+ko</tex>
| <tex>t+(k+1)o</tex>
| <tex>\ldots</tex>
| <tex>t-o \ldots</tex>
| <tex>\ldots</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>t+(k+1)o</tex>
| <tex>t+ko \ldots t</tex>
| <tex>t-o \ldots</tex>
| <tex>\ldots</tex>
| <tex>\ldots</tex>
|}
{| border="1" style="border-collapse: collapse; float: left; margin-right: 30px; text-align: center;"
| colspan="4" style="text-align: center"| <tex>h</tex>
|-
| <tex>t \ldots t+ko</tex>
| <tex>\ldots</tex>
| <tex>t+(k+1)o \ldots</tex>
| <tex>\ldots</tex>
|-
| <tex>t+ko \ldots t</tex>
| <tex>\ldots</tex>
| <tex>t+(k+1)o \ldots</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>t \ldots t+ko</tex>
| <tex>t+(k+1)o \ldots</tex>
| <tex>\ldots</tex>
|}
{| border="1" style="border-collapse: collapse; text-align: center;"
| colspan="4" style="text-align: center"| <tex>k</tex>
|-
| <tex>t \ldots t+ko</tex>
| <tex>\ldots</tex>
| <tex>\ldots t+(k+1)o</tex>
| <tex>\ldots</tex>
|-
| <tex>t+(k+1)o \ldots</tex>
| <tex>\ldots</tex>
| <tex>t+ko \ldots t</tex>
| <tex>\ldots</tex>
|-
| <tex>\ldots</tex>
| <tex>\ldots t+(k+1)o</tex>
| <tex>t+ko \ldots t</tex>
| <tex>\ldots</tex>
|}
=== Корректность алгоритма ===
{{Теорема
|statement=Предложенный алгоритм создает перестановку с <tex>n-1</tex> соседствами не более чем за <tex>\dfrac{5n-7}{3}</tex> итераций.
|proof=
Алгоритм всегда завершит работу. На каждой итерации при условии, что в перестановке меньше <tex>n-1</tex> соседств, выполнится одно из условий <tex>1-7</tex>. На каждой итерации создается не меньше одного соседства и ни одного соседства не разрушается, поэтому алгоритм создаст нужную перестановку не больше чем за <tex>n-1</tex> итераций.
Будем называть случай 1 ''действием 1'', случай 2 ''действием 2'', случаи 3 и 6 ''действием 3'', случаи 4, 5 и 7 ''действиями'' 4, 5 и 7 соответственно. Пусть <tex>x_i</tex> обозначает количество действий типа <tex>i</tex>, выполненных за время работы алгоритма. Суммарное число разворотов составит
<tex>z=x_1 + x_2 + 4x_3 + x_4 + 2x_5 + x_7</tex>
<tex>x_i</tex> умножено на количество разворотов, выполняемых за это действие.
Действие 3 может быть разделено на 4 случая. Перед предпоследним разворотом самый левый элемент массива и элемент после <tex>t-o</tex> могут
# Быть непарными.
# Образовывать новый блок.
# Соединять блок с отдельным элементом.
# Соединять два блока.
Эти 4 варианта учитываются, если считать <tex>x_3 = x_{31}+x_{32}+x_{33}+x_{34}</tex>. В таблице 1 записано, как каждое действие увеличивается количество соседств. Суммарное количество соседств можно записать в виде суммы
<tex>n-1 = a + x_1 + x_2 + 2x_{31} + 3x_{32} + 3x_{33} + 3x_{34} + x_4 + x_5 + x_7</tex>
Если <tex>b</tex> {{---}} количество блоков в изначальной перестановке, то, поскольку каждое действие изменяет количество блоков так, как показано в таблице 1, а в конечной перестановке 1 блок, имеем
<tex>b + x_1 - x_{31} - x_{33} - 2x_{34} - x_5 - x_7 = 1</tex>
Поскольку <tex>b\leqslant a</tex>, из первого равенства следует
<tex>x_1 + x_2 + 2x_{31} + 3x_{32} + 3x_{33} + 3x_{34} + x_4 + x_5 + x_7 + b \leqslant n-1</tex>
Таким образом, для нахождения худшего случая нужно максимизировать
<tex>z=x_1 + x_2 + 4x_3 + x_4 + 2x_5 + x_7</tex>
так, чтобы выполнялось равенство
<tex>b + x_1 - x_{31} - x_{33} - 2x_{34} - x_5 - x_7 = 1</tex>
и неравенство
<tex>x_1 + x_2 + 2x_{31} + 3x_{32} + 3x_{33} + 3x_{34} + x_4 + x_5 + x_7 + b \leqslant n-1</tex>
Утверждается, что максимальное значение достигается при
<tex>x_1 = \dfrac{n+1}{3}</tex>, <tex>x_2 = 0</tex>, <tex>x_3 = x_{31} = \dfrac{n-2}{3}</tex>, <tex>x_4=x_5=x_7=b=0</tex>
В таком случае максимизируемое значение <tex>z=\dfrac{5n-7}{3}</tex>. Для доказательства этого утверждения воспользуемся теоремой о двойственности Данцига-фон Неймана, из которой следует, что максимальное значение равно минимальному значению двойной линейной задачи:
минимизировать <tex>\omega=\xi_2+(n-1)\xi_3</tex>
при условиях
<tex>\xi_2+\xi_3 \geqslant 1</tex>,
<tex>\xi_3 \geqslant 1</tex>,
<tex>-\xi_2+2\xi_3 \geqslant 4</tex>,
<tex>3\xi_3 \geqslant 4</tex>,
<tex>-\xi_2+3\xi_3 \geqslant 4</tex>,
<tex>-2\xi_2+3\xi_3 \geqslant 4</tex>,
<tex>\xi_3 \geqslant 1</tex>,
<tex>-\xi_2+\xi_3 \geqslant 1</tex>,
<tex>-\xi_2+\xi_3 \geqslant 2</tex>,
<tex>\xi_2+\xi_3 \geqslant 0</tex>.
Для доказательства утверждения достаточно найти пару <tex>(\xi_2, \xi_3)</tex>, удовлетворяющую этим условиям, при которой <tex>\omega=\xi_2+(n-1)\xi_3=\dfrac{5n-7}{3}</tex>. Такая пара {{---}} <tex>(-\dfrac{2}{3}, \dfrac{5}{3})</tex>.
Граница <tex>\dfrac{5n+5}{3}</tex> получается прибавлением <tex>4</tex> лишних действий, нужных, чтобы добавить последнее соседство. Алгоритм для этого был описан выше.
}}
{| class="wikitable" style="text-align: center"
| colspan="10" | Таблица 1
|-
| Действие || <tex>1</tex> || <tex>2</tex> || <tex>31</tex> || <tex>32</tex> || <tex>33</tex> || <tex>34</tex> || <tex>4</tex> || <tex>5</tex> || <tex>7</tex>
|-
| Количество разворотов || <tex>1</tex> || <tex>1</tex> || <tex>4</tex> || <tex>4</tex> || <tex>4</tex> || <tex>4</tex> || <tex>1</tex> || <tex>2</tex> || <tex>1</tex>
|-
| Увеличение количества соседств || <tex>1</tex> || <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>3</tex> || <tex>3</tex> || <tex>1</tex> || <tex>1</tex> || <tex>1</tex>
|-
| Изменение количества блоков || <tex>1</tex> || <tex>0</tex> || <tex>-1</tex> || <tex>0</tex> || <tex>-1</tex> || <tex>-2</tex> || <tex>0</tex> || <tex>-1</tex> || <tex>-1</tex>
|}
==== Нижняя ====
Для нижней границы построим последовательность, которая может быть отсортирована не менее чем за <tex>\dfrac{17n}{16}</tex> разворотов.
Пусть <tex>\tau = 17536428</tex>. Для положительного целого <tex>k</tex> будем обозначать <tex>\tau</tex>, в которой каждое число увеличено на <tex>8(k-1)</tex>, как <tex>\tau_k</tex>. Другими словами, <tex>\tau_k = 1_k 7_k 5_k 3_k 6_k 4_k 2_k 8_k</tex>, где <tex>m_k = m+8(k-1)</tex>. Пусть перестановка <tex>\chi = \tau_1 \tau_2^R \tau_3 \tau_4^R \ldots \tau_{m-1} \tau_m^R</tex>, где <tex>m</tex> {{---}} чётное целое число, и пусть <tex>n=|\chi |=8m</tex>.
{{Теорема
|statement=Число разворотов, необходимое для сортировки последовательности <tex>\chi</tex>, не меньше <tex>\dfrac{17n}{16}</tex>.
}}
== Задача о подгоревших блинах ==
Изначально задача по подгоревших блинах (англ. ''burnt pancake problem'') формулировалась так:
Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.
Другими словами, нужно предложить алгоритм блинной сортировки, в котором каждый элемент будет развёрнут чётное число раз.
== См. также ==
* [[Timsort | Timsort]]
* [[Быстрая сортировка | Быстрая сортировка]]
== Источники информации ==
*[https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 Wikipedia: Блинная сортировка]
*[http://www.eecs.berkeley.edu/~christos/papers/GP79.pdf William H. Gates; Christos H. Papadimitriou Bounds for sorting by prefix reversal]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Другие сортировки]]
