Изменения
Нет описания правки
Для начала покажем, что любую последовательность можно отсортировать с помощью блинной сортировки. Для этого будет предложен алгоритм, позволяющий отсортировать любой массив, сделав не более <tex>2n</tex> операций, где <tex>n</tex> {{---}} размер массива.
Найдём максимальный элемент последовательности с номером <tex>i</tex> и развернём префикс массива до <tex>i</tex>-ого элемента. Теперь максимальный элемент находится в начале массива. Развернём весь массив, теперь максимальный элемент находится в конце массива. Сделаем то же самое рекуррентно для префикса длины <tex>n-1</tex>. Переместим второй по возрастанию элемент в конец подотрезка, после чего последние два элемента будут отсортированы, и продолжим для префикса длины <tex>n-2</tex>. Таким образом, на каждой итерации мы сделаем 2 две операции, и всего итераций будет не больше <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>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>\rightarrow</tex> из <tex>R: \Sigma^*_n</tex> в <tex>\rightarrow \Sigma^*_n</tex>: <tex>\pi\rightarrowR\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 \rightarrow R \pi_1 \rightarrow R \ldots \rightarrow 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>.
{| 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>
{| border="1" style="border-collapse: collapse;"
| colspan="2" style="text-align: center" | <tex>b</tex>
|-
| style="text-align: right" | <tex>k\ldots n</tex>
|}
=== Алгоритм ===
'''Алгоритм''':
|}
=== Корректность алгоритма ===
{{Теорема
|statement=Предложенный алгоритм создает перестановку с <tex>n-1</tex> соседством не более чем за <tex>\fracdfrac{5n-7}{3}</tex> итераций.
|proof=
Алгоритм всегда завершит работу. На каждой итерации при условии, что в перестановке меньше <tex>n-1</tex> соседств, выполнится одно из условий <tex>1-7</tex>. На каждой итерации создается не меньше одного соседства и ни одного соседства не разрушается, поэтому алгоритм создаст нужную перестановку не больше чем за <tex>n-1</tex> итерацию.
Будем называть случай <tex>1</tex> ''действием 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>
Действие 3 может быть разделено на 4 случая. Перед предпоследним разворотом самый левый элемент массива и элемент после <tex>t-o</tex> могут
# быть Быть непарными,.# образовывать Образовывать новый блок,.# соединять Соединять блок с отдельным элементом,.# соединять Соединять два блока.
Эти 4 варианта учитываются, если считать <tex>x_3 = x_{31}+x_{32}+x_{33}+x_{34}</tex>. В таблице 1 записано, как каждое действие увеличивается количество соседств. Суммарное количество соседств можно записать в виде суммы
Утверждается, что максимальное значение достигается при
<tex>x_1 = \fracdfrac{n+1}{3}</tex>, <tex>x_2 = 0</tex>, <tex>x_3 = x_{31} = \fracdfrac{n-2}{3}</tex>, <tex>x_4=x_5=x_7=b=0</tex>
В таком случае максимизируемое значение <tex>z=\fracdfrac{5n-7}{3}</tex>. Для доказательства этого утверждения воспользуемся теоремой о двойственности Данцига-фон Неймана, из которой следует, что максимальное значение равно минимальному значению двойной линейной задачи:
минимизировать <tex>\omega=\xi_2+(n-1)\xi_3</tex>
<tex>\xi_2+\xi_3 \geqslant 0</tex>.
Для доказательства утверждения достаточно найти пару <tex>(\xi_2, \xi_3)</tex>, удовлетворяющую этим условиям, при которой <tex>\omega=\xi_2+(n-1)\xi_3=\fracdfrac{5n-7}{3}</tex>. Такая пара {{---}} <tex>(-\fracdfrac{2}{3}, \fracdfrac{5}{3})</tex>.
Граница <tex>\fracdfrac{5n+5}{3}</tex> получается прибавлением <tex>4</tex> лишних действий, нужных, чтобы добавить последнее соседство. Алгоритм для этого был описан выше.
==== Нижняя ====
Для нижней границы построим последовательность, которая может быть отсортирована не менее чем за <tex>\fracdfrac{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>m</tex> <tex>f(\chi ) \geqslant \fracdfrac{17n}{16}</tex>
}}
== См. также ==
* [[Сортировки Timsort | СортировкиTimsort]]* [[Быстрая сортировка | Быстрая сортировка]]
== Источники информации ==
*[http://www.eecs.berkeley.edu/~christos/papers/GP79.pdf William H. Gates; Christos H. Papadimitriou Bounds for sorting by prefix reversal]
[[Категория: СортировкаСортировки]]
