Блинная сортировка

Блинная сортировка (англ. 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] могут Быть непарными. Образовывать новый блок. Соединять блок с отдельным элементом. Соединять два блока. Эти 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]f(\chi ) \geqslant \dfrac{17n}{16}[/math]

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

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

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

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

См. также

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

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

• Wikipedia: Блинная сортировка
• William H. Gates; Christos H. Papadimitriou Bounds for sorting by prefix reversal