Изменения

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

Найдём максимальный элемент последовательности с номером <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 действия (в иллюстрациях дальше показана последовательность действий, состояние в следующей строке получается из состояния в предыдущей одним разворотом префикса):

|statement=Предложенный алгоритм создает перестановку с <tex>n-1</tex> соседством соседствами не более чем за <tex>\dfrac{5n-7}{3}</tex> итераций.

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