Pancake Sort

Проблема

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

Решение

На каждом шаге рассматривается ещё не отсортированный префикс массива размером size (изначально - весь массив). В нём находится позиция максимального элемента. Если максимум уже стоит в конце этого префикса - переходим к следующему, уменьшенному префиксу. Иначе выполняются два переворота: сначала переворачивается префикс до позиции максимума (это переносит максимум на самый верх, то есть в начало массива), затем переворачивается весь префикс размера size (это переносит максимум с начала прямо на последнюю позицию префикса - его законное место). После этого size уменьшается на единицу, и процесс повторяется для оставшейся неотсортированной части.

Как это работает

Проверим числа на конкретном входе - том же массиве [8, 3, 9, 1, 6, 4, 7, 2, 5] (n = 9), что используется на вкладке «Визуализация». Симуляция кода с вкладки «Реализация» даёт: 36 сравнений и 14 переворотов до полной сортировки.

36 - это не случайное число: поиск максимума на каждой итерации всегда просматривает весь текущий префикс целиком, независимо от того, насколько массив уже упорядочен. Сумма 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 - в точности n(n-1)/2 для n = 9. Это подтверждается прямым замером: на уже отсортированном [1..9] алгоритм тоже делает ровно 36 сравнений, хотя не выполняет вообще ни одного переворота (0 flips) - максимум всегда уже на месте.

Это значит, что в отличие от многих сортировок сравнением, у блинной сортировки нет лучшего случая по числу сравнений - она всегда Θ(n²), а не O(n) на отсортированном входе, как у insertion sort или bubble sort с ранним выходом. Причина - на строке 15-18 JS-реализации нет условия для остановки поиска максимума раньше времени, даже если он найден в самом начале префикса.

Число переворотов, наоборот, сильно зависит от входа - и не всегда предсказуемым образом. Развёрнутый массив [9..1] кажется «худшим случаем», но даёт всего 1 переворот: на первой итерации максимум (9) уже стоит на позиции 0, поэтому первый flip пропускается (строка 20), а единственный flip(size - 1) разворачивает весь массив целиком - и развёрнутый убывающий массив после одного полного разворота сразу становится отсортированным по возрастанию. Дальше на каждой итерации максимум уже на месте, флипов больше не требуется.

Настоящий худший случай по числу флипов не так очевиден. Полный перебор всех 720 перестановок [1..6] (n = 6) находит максимум в 9 переворотов - например, на входе [1, 5, 2, 3, 6, 4] - против теоретической верхней границы 2(n-1) = 10. Граница 2(n-1) не достигается на каждом входе, но остаётся верной верхней оценкой: не более двух переворотов на каждую из n - 1 итераций внешнего цикла.

Важно не путать этот 2(n-1) - верхнюю границу для конкретного жадного алгоритма, показанного здесь, - с открытой «блинной задачей» (pancake problem): нахождением минимально возможного числа переворотов для произвольной перестановки любым алгоритмом. Билл Гейтс и Христос Пападимитриу в статье 1979 года улучшили известную на тот момент оценку минимума до (5n + 5) / 3 переворотов в худшем случае - точная минимальная формула не найдена до сих пор, а для «подгоревшей» версии задачи (pancake flipping with burnt side) она и вовсе доказана NP-трудной.

Итог: сравнения у блинной сортировки всегда квадратичны по построению (n(n-1)/2, не зависит от порядка входа), а переворотов - от нуля (уже отсортированный или, как показано выше, даже полностью развёрнутый вход) до порядка 2n. Асимптотический класс O(n²) определяется именно сравнениями, а не флипами - урок о том, что ограниченный набор разрешённых операций (здесь - только переворот префикса) может сделать структуру сложности алгоритма нетипичной по сравнению с более гибкими сортировками.

Нюансы выбора

Против сортировки выбором - те же n(n-1)/2 сравнений и тот же принцип «найти максимум, поставить на место», но выбором элемент переносится одним обменом, а здесь - до двух переворотов; выбирайте pancake sort только когда операция обмена произвольных элементов физически недоступна.

Не ожидать лучшего случая на отсортированном входе - как показано в разборе выше, число сравнений (36 при n = 9) не меняется вообще, независимо от порядка входа; выигрыш от порядка виден только в числе переворотов, а не во времени поиска максимума.

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

Не путать жадный алгоритм с открытой «блинной задачей» - если задача требует именно минимального числа переворотов (а не просто корректной сортировки), показанный здесь алгоритм не даёт оптимума; минимизация - отдельная, значительно более сложная NP-трудная задача.

Примеры в коде

Оценка Гейтса и Пападимитриу `(5n + 5) / 3` (1979) десятилетиями оставалась одной из наиболее влиятельных верхних границ для минимального числа переворотов в блинной задаче - на неё до сих пор ссылаются как на отправную точку почти все последующие работы по этой теме.

«Подгоревшая» блинная задача (burnt pancake problem), где каждый блин ещё и имеет сторону (подгоревшую и нет), а переворот меняет их местами, моделирует задачи реверсии со знаком в геномике - обобщение того же приёма переворота сегмента, но с направленностью элементов.

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

Робототехнические и промышленные системы с ограниченным захватом (например, конвейеры, способные только «перевернуть верхний блок стопки», а не переставить произвольные элементы) - редкий, но реальный класс физических систем, где модель pancake sort соответствует буквальному ограничению оборудования.

Когда применять

• Когда единственная доступная операция - это переворот префикса (например, задачи с ограничением на модель вычислений или роботизированные системы, физически способные только «перевернуть верхний блок»).
• Как учебный пример для изучения NP-трудной «блинной задачи» и того, как ограниченный набор операций всё ещё позволяет достичь полной сортировки.

Примеры из практики

• Ранняя статья Билла Гейтса и Христоса Пападимитриу (1979) предложила алгоритм и оценку числа переворотов для «блинной задачи», ставшую классической в теории алгоритмов.
• Перестройка сегментов ДНК в биоинформатике моделируется похожей задачей о развороте (сортировка перестановок реверсиями) - переворот отрезка последовательности вместо отдельных перестановок элементов.