Блинная сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удалено содержимое страницы)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 3 участников)
Строка 1: Строка 1:
  
 +
'''Блинная сортировка''' (англ. ''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]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Сортировки]]
 +
[[Категория: Другие сортировки]]

Текущая версия на 19:35, 4 сентября 2022

Блинная сортировка (англ. pancake sorting) — алгоритм сортировки с помощью одной операции — переворота элементов последовательности до какого-то индекса (префикса последовательности). Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.

Корректность

Для начала покажем, что любую последовательность можно отсортировать с помощью блинной сортировки. Для этого будет предложен алгоритм, позволяющий отсортировать любой массив, сделав не более [math]2n[/math] операций, где [math]n[/math] — размер массива.

Найдём максимальный элемент последовательности с номером [math]i[/math] и развернём префикс массива до [math]i[/math]-го элемента. Теперь максимальный элемент находится в начале массива. Развернём весь массив, теперь максимальный элемент находится в конце массива. Сделаем то же самое рекуррентно для префикса длины [math]n-1[/math]. Переместим второй по возрастанию элемент в конец подотрезка, после чего последние два элемента будут отсортированы, и продолжим для префикса длины [math]n-2[/math]. Таким образом, на каждой итерации мы сделаем две операции, и всего итераций будет не больше [math]n[/math] (их может быть меньше [math]n[/math]: если после [math]i[/math]-ой итерации отсортированным окажется суффикс длины больше, чем [math]i+1[/math], можно рекурсивно запустить алгоритм на префиксе длины [math]n-i-k[/math] вместо [math]n-i-1[/math]). Тогда суммарное количество операций не превосходит [math]2n[/math] и любая последовательность может быть отсортирована таким образом.

Оценки на количество операций

Существуют простые оценки: [math]2n[/math] сверху и, для [math]n \geqslant 4[/math], [math]n[/math] снизу. Более сложные границы были предложены в 1978 году Биллом Гейтсом и Христосом Пападимитриу, и улучшить их получилось лишь в 2008.

Наивные

Верхняя

Оценка в [math]2n[/math] операций следует из доказательства корректности алгоритма, в котором предлагается алгоритм сортировки любой последовательности за [math]2n[/math] операций. Она может быть улучшена до [math]2n-3[/math] чуть более умной сортировкой последних элементов.

Нижняя

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

Для любого [math]n\geqslant 4[/math] существует массив, в котором нет соседств. С другой стороны, отсортированный массив имеет [math]n[/math] соседств, и за один переворот можно добавить не больше одного соседства, поэтому отсортировать массив, сделав меньше, чем [math]n[/math] переворотов, невозможно.

Продвинутые

Для начала введём некоторые обозначения.

Пусть [math]S_n[/math] — множество перестановок элементов массива длины [math]n[/math]. Будем считать перестановки строками в [math]\Sigma^*_n[/math], где [math]\Sigma_n=\{1, 2, \ldots, n\}[/math]. Введём бинарное отношение [math]R: \Sigma^*_n \rightarrow \Sigma^*_n[/math]: [math]\pi R\sigma[/math] тогда и только тогда, когда [math]\pi =xy[/math] и [math]\sigma =x^Ry[/math], где [math]\pi, \sigma \in \Sigma^*_n[/math] и [math]x^R[/math] обозначает развёрнутую [math]x[/math].

Пусть [math]\pi[/math] — перестановка, тогда [math]f(\pi)[/math] — наименьшее [math]k[/math] такое, что существует последовательность перестановок [math]\pi_0 R \pi_1 R \ldots R \pi_k = e_n[/math], где [math]e_n = 123\ldots n[/math]. Тогда для числа [math]n[/math] будем обозначать [math]f(n)[/math] за максимальное [math]f(\pi)[/math] среди всех [math]\pi \in S_n[/math].

Пусть [math]\pi[/math] — перестановка из [math]S_n[/math]. Тогда [math]\pi (j)[/math] — число номер [math]j[/math] в перестановке для [math]1 \leqslant j \leqslant n[/math]. Соседством в [math]\pi[/math] назовём пару [math](j, j+1)[/math] такую, что [math]|\pi (j) - \pi (j+1)| = 1[/math]. Также будем называть соседством пару [math](j, j+1)[/math], если [math]\{\pi (j), \pi (j+1) \} = \{1, n\}[/math]. Для [math]x \in \Sigma^*_n[/math] будем обозначать длину [math]x[/math] как [math]|x|[/math].

Пусть [math]\pi=xby[/math], [math]x, b, y \in \Sigma^*_n[/math]. [math]b[/math] будем называть блоком, если для любого [math]j[/math] такого, что [math]|x|+1 \leqslant j \leqslant |x| + |b| - 1[/math], пара [math](j, j+1)[/math] — соседство, при этом пары [math](|x|, |x|+1)[/math] и [math](|x|+|b|-1, |x|+|b|[/math] не являются соседствами. Если [math]\pi (j)[/math] не является частью блока, то есть [math](j-1, j)[/math] и [math](j, j+1)[/math] — не соседства, элемент [math]\pi (j)[/math] будем называть свободным.

За [math]o[/math] будем обозначать элемент из [math]\{-1, 1\}[/math]. Подразумевается, что сложение проводится по модулю [math]n[/math].

Верхняя

Будет предложен алгоритм, который изменит перестановку [math]\pi[/math] так, чтобы в ней было [math]n-1[/math] соседств. После этого отсортировать массив можно не более чем за 4 действия (в иллюстрациях дальше показана последовательность действий, состояние в следующей строке получается из состояния в предыдущей одним разворотом префикса):

[math]a[/math]
[math]k-1 \ldots 1[/math] [math]n \ldots k[/math]
[math]k\ldots n[/math] [math]1\ldots k-1[/math]
[math]n\ldots k[/math] [math]1 \ldots k-1[/math]
[math]k-1 \ldots 1[/math] [math]k \ldots n[/math]
[math]1 \ldots k-1[/math] [math]k \ldots n[/math]
[math]b[/math]
[math]k\ldots n[/math] [math]1\ldots k-1[/math]
[math]n\ldots k[/math] [math]1\ldots k-1[/math]
[math]k-1 \ldots 1[/math] [math]k\ldots n[/math]
[math]1\ldots k-1[/math] [math]k\ldots n[/math]


Алгоритм

Алгоритм:

  • входные данные: перестановка [math]\pi\in S_n[/math]
  • выходные данные: перестановка [math]\sigma[/math] с [math]n-1[/math] соседством

Циклически повторять следующее. Пусть [math]t[/math] — первый элемент [math]\pi[/math] ([math]\pi = t\pi '[/math]). Как минимум одно из условий выполняется, выполнить соответствующее действие:

  1. [math]t[/math] свободный, [math]t+o[/math] свободный. Выполнить разворот [math]a[/math],
  2. [math]t[/math] свободный, [math]t+o[/math] — первый элемент блока. Выполнить разворот [math]b[/math],
  3. [math]t[/math] свободный, и [math]t+1[/math], и [math]t-1[/math] — последние элементы в блоке. Выполнить развороты [math]c[/math],
  4. [math]t[/math] в блоке, [math]t+o[/math] свободен. Выполнить разворот [math]d[/math],
  5. [math]t[/math] в блоке, [math]t+o[/math] — первый элемент блока. Выполнить разворот [math]e[/math],
  6. [math]t[/math] в блоке с последним элементом [math]t+k\cdot o[/math] ([math]k\gt 0[/math]), [math]t-o[/math] — последний элемент другого блока, и [math]t+(k+1)\cdot o[/math] свободен. Выполнить перевороты [math]f[/math] или [math]g[/math] в зависимости от расположения блоков,
  7. [math]t[/math] в блоке с последним элементом [math]t+k\cdot o[/math] ([math]k\gt 0[/math]), [math]t-o[/math] — последний элемент другого блока, и [math]t+(k+1)\cdot o[/math] в блоке. Выполнить развороты [math]h[/math] или [math]k[/math] в зависимости от того, в начале или в конце блока находится элемент [math]t+(k+1)\cdot o[/math],
  8. ничего из перечисленного выше. В перестановке [math]\pi[/math] [math]n-1[/math] соседство. Завершить работу алгоритма.

Необходимые развороты:

[math]a[/math]
[math]t[/math] [math]\ldots[/math] [math]t+o[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]t[/math] [math]t+o[/math] [math]\ldots[/math]
[math]b[/math]
[math]t[/math] [math]\ldots[/math] [math]t+o\ldots[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]t[/math] [math]t+o\ldots[/math] [math]\ldots[/math]
[math]c[/math]
[math]t[/math] [math]\ldots[/math] [math]\ldots t+o[/math] [math]\ldots[/math] [math]\ldots t-o[/math] [math]\ldots[/math]
[math]t+o\ldots[/math] [math]\ldots[/math] [math]t[/math] [math]\ldots[/math] [math]\ldots t-o[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]\ldots t+o[/math] [math]t[/math] [math]\ldots[/math] [math]\ldots t-o[/math] [math]\ldots[/math]
[math]t-o \ldots[/math] [math]\ldots[/math] [math]t[/math] [math]t+o \ldots[/math] [math]\ldots[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]\ldots t-o[/math] [math]t[/math] [math]t+o \ldots[/math] [math]\ldots[/math] [math]\ldots[/math]
[math]d[/math]
[math]t\ldots[/math] [math]\ldots[/math] [math]t+o[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]\ldots t[/math] [math]t+o[/math] [math]\ldots[/math]
[math]e[/math]
[math]t\ldots[/math] [math]\ldots[/math] [math]t+o\ldots[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]\ldots t[/math] [math]t+o \ldots[/math] [math]\ldots[/math]




[math]f[/math]
[math]t\ldots t+ko[/math] [math]\ldots[/math] [math]t+(k+1)o[/math] [math]\ldots[/math] [math]\ldots t-o[/math] [math]\ldots[/math]
[math]t+(k+1)o[/math] [math]\ldots[/math] [math]t+ko\ldots t[/math] [math]\ldots[/math] [math]\ldots t-o[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]t+(k+1)o[/math] [math]t+ko\ldots t[/math] [math]\ldots[/math] [math]\ldots t-o[/math] [math]\ldots[/math]
[math]t-o \ldots[/math] [math]\ldots[/math] [math]t \ldots t+ko[/math] [math]t+(k+1)o[/math] [math]\ldots[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]\ldots t-o[/math] [math]t \ldots t+ko[/math] [math]t+(k+1)o[/math] [math]\ldots[/math] [math]\ldots[/math]
[math]g[/math]
[math]t \ldots t+ko[/math] [math]\ldots[/math] [math]\ldots t-o[/math] [math]\ldots[/math] [math]t+(k+1)o[/math] [math]\ldots[/math]
[math]t+(k+1)o[/math] [math]\ldots[/math] [math]t-o \ldots[/math] [math]\ldots[/math] [math]t+ko \ldots t[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]\ldots to[/math] [math]\ldots[/math] [math]t+(k+1)o[/math] [math]t+ko \ldots t[/math] [math]\ldots[/math]
[math]t \ldots t+ko[/math] [math]t+(k+1)o[/math] [math]\ldots[/math] [math]t-o \ldots[/math] [math]\ldots[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]t+(k+1)o[/math] [math]t+ko \ldots t[/math] [math]t-o \ldots[/math] [math]\ldots[/math] [math]\ldots[/math]


[math]h[/math]
[math]t \ldots t+ko[/math] [math]\ldots[/math] [math]t+(k+1)o \ldots[/math] [math]\ldots[/math]
[math]t+ko \ldots t[/math] [math]\ldots[/math] [math]t+(k+1)o \ldots[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]t \ldots t+ko[/math] [math]t+(k+1)o \ldots[/math] [math]\ldots[/math]
[math]k[/math]
[math]t \ldots t+ko[/math] [math]\ldots[/math] [math]\ldots t+(k+1)o[/math] [math]\ldots[/math]
[math]t+(k+1)o \ldots[/math] [math]\ldots[/math] [math]t+ko \ldots t[/math] [math]\ldots[/math]
[math]\ldots[/math] [math]\ldots t+(k+1)o[/math] [math]t+ko \ldots t[/math] [math]\ldots[/math]

Корректность алгоритма

Теорема:
Предложенный алгоритм создает перестановку с [math]n-1[/math] соседствами не более чем за [math]\dfrac{5n-7}{3}[/math] итераций.
Доказательство:
[math]\triangleright[/math]

Алгоритм всегда завершит работу. На каждой итерации при условии, что в перестановке меньше [math]n-1[/math] соседств, выполнится одно из условий [math]1-7[/math]. На каждой итерации создается не меньше одного соседства и ни одного соседства не разрушается, поэтому алгоритм создаст нужную перестановку не больше чем за [math]n-1[/math] итераций.

Будем называть случай 1 действием 1, случай 2 действием 2, случаи 3 и 6 действием 3, случаи 4, 5 и 7 действиями 4, 5 и 7 соответственно. Пусть [math]x_i[/math] обозначает количество действий типа [math]i[/math], выполненных за время работы алгоритма. Суммарное число разворотов составит

[math]z=x_1 + x_2 + 4x_3 + x_4 + 2x_5 + x_7[/math]

[math]x_i[/math] умножено на количество разворотов, выполняемых за это действие.

Действие 3 может быть разделено на 4 случая. Перед предпоследним разворотом самый левый элемент массива и элемент после [math]t-o[/math] могут

  1. Быть непарными.
  2. Образовывать новый блок.
  3. Соединять блок с отдельным элементом.
  4. Соединять два блока.

Эти 4 варианта учитываются, если считать [math]x_3 = x_{31}+x_{32}+x_{33}+x_{34}[/math]. В таблице 1 записано, как каждое действие увеличивается количество соседств. Суммарное количество соседств можно записать в виде суммы

[math]n-1 = a + x_1 + x_2 + 2x_{31} + 3x_{32} + 3x_{33} + 3x_{34} + x_4 + x_5 + x_7[/math]

Если [math]b[/math] — количество блоков в изначальной перестановке, то, поскольку каждое действие изменяет количество блоков так, как показано в таблице 1, а в конечной перестановке 1 блок, имеем

[math]b + x_1 - x_{31} - x_{33} - 2x_{34} - x_5 - x_7 = 1[/math]

Поскольку [math]b\leqslant a[/math], из первого равенства следует

[math]x_1 + x_2 + 2x_{31} + 3x_{32} + 3x_{33} + 3x_{34} + x_4 + x_5 + x_7 + b \leqslant n-1[/math]

Таким образом, для нахождения худшего случая нужно максимизировать

[math]z=x_1 + x_2 + 4x_3 + x_4 + 2x_5 + x_7[/math]

так, чтобы выполнялось равенство

[math]b + x_1 - x_{31} - x_{33} - 2x_{34} - x_5 - x_7 = 1[/math]

и неравенство

[math]x_1 + x_2 + 2x_{31} + 3x_{32} + 3x_{33} + 3x_{34} + x_4 + x_5 + x_7 + b \leqslant n-1[/math]

Утверждается, что максимальное значение достигается при

[math]x_1 = \dfrac{n+1}{3}[/math], [math]x_2 = 0[/math], [math]x_3 = x_{31} = \dfrac{n-2}{3}[/math], [math]x_4=x_5=x_7=b=0[/math]

В таком случае максимизируемое значение [math]z=\dfrac{5n-7}{3}[/math]. Для доказательства этого утверждения воспользуемся теоремой о двойственности Данцига-фон Неймана, из которой следует, что максимальное значение равно минимальному значению двойной линейной задачи:

минимизировать [math]\omega=\xi_2+(n-1)\xi_3[/math]

при условиях

[math]\xi_2+\xi_3 \geqslant 1[/math],

[math]\xi_3 \geqslant 1[/math],

[math]-\xi_2+2\xi_3 \geqslant 4[/math],

[math]3\xi_3 \geqslant 4[/math],

[math]-\xi_2+3\xi_3 \geqslant 4[/math],

[math]-2\xi_2+3\xi_3 \geqslant 4[/math],

[math]\xi_3 \geqslant 1[/math],

[math]-\xi_2+\xi_3 \geqslant 1[/math],

[math]-\xi_2+\xi_3 \geqslant 2[/math],

[math]\xi_2+\xi_3 \geqslant 0[/math].

Для доказательства утверждения достаточно найти пару [math](\xi_2, \xi_3)[/math], удовлетворяющую этим условиям, при которой [math]\omega=\xi_2+(n-1)\xi_3=\dfrac{5n-7}{3}[/math]. Такая пара — [math](-\dfrac{2}{3}, \dfrac{5}{3})[/math].

Граница [math]\dfrac{5n+5}{3}[/math] получается прибавлением [math]4[/math] лишних действий, нужных, чтобы добавить последнее соседство. Алгоритм для этого был описан выше.
[math]\triangleleft[/math]
Таблица 1
Действие [math]1[/math] [math]2[/math] [math]31[/math] [math]32[/math] [math]33[/math] [math]34[/math] [math]4[/math] [math]5[/math] [math]7[/math]
Количество разворотов [math]1[/math] [math]1[/math] [math]4[/math] [math]4[/math] [math]4[/math] [math]4[/math] [math]1[/math] [math]2[/math] [math]1[/math]
Увеличение количества соседств [math]1[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]3[/math] [math]3[/math] [math]1[/math] [math]1[/math] [math]1[/math]
Изменение количества блоков [math]1[/math] [math]0[/math] [math]-1[/math] [math]0[/math] [math]-1[/math] [math]-2[/math] [math]0[/math] [math]-1[/math] [math]-1[/math]

Нижняя

Для нижней границы построим последовательность, которая может быть отсортирована не менее чем за [math]\dfrac{17n}{16}[/math] разворотов.

Пусть [math]\tau = 17536428[/math]. Для положительного целого [math]k[/math] будем обозначать [math]\tau[/math], в которой каждое число увеличено на [math]8(k-1)[/math], как [math]\tau_k[/math]. Другими словами, [math]\tau_k = 1_k 7_k 5_k 3_k 6_k 4_k 2_k 8_k[/math], где [math]m_k = m+8(k-1)[/math]. Пусть перестановка [math]\chi = \tau_1 \tau_2^R \tau_3 \tau_4^R \ldots \tau_{m-1} \tau_m^R[/math], где [math]m[/math] — чётное целое число, и пусть [math]n=|\chi |=8m[/math].

Теорема:
Число разворотов, необходимое для сортировки последовательности [math]\chi[/math], не меньше [math]\dfrac{17n}{16}[/math].

Задача о подгоревших блинах

Изначально задача по подгоревших блинах (англ. burnt pancake problem) формулировалась так:

Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.

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

См. также

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