Изменения
Нет описания правки
'''Блинная сортировка''' (англ. ''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>\pi</tex> так, чтобы в ней было <tex>n-1</tex> соседствососедств. После этого отсортировать массив можно не более чем за 4 действия (в иллюстрациях дальше показана последовательность действий, состояние в следующей строке получается из состояния в предыдущей одним разворотом префикса):
{| border="1" style="border-collapse: collapse; float: left; margin-right: 30px;"
{{Теорема
|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>, выполненных за время работы алгоритма. Суммарное число разворотов составит
{{Теорема
|statement=Число разворотов, необходимое для сортировки последовательности <tex>\chi</tex>, не меньше <tex>\dfrac{17n}{16}</tex>.
}}
*[http://www.eecs.berkeley.edu/~christos/papers/GP79.pdf William H. Gates; Christos H. Papadimitriou Bounds for sorting by prefix reversal]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Другие сортировки]]
