Pancake Sort

Pancake Sort — сортировка "блинов": единственная операция — переворот префикса массива.

Основная идея

На каждой итерации находим максимум в неотсортированной части, переворотом перемещаем его в начало, затем переворачиваем весь префикс, чтобы он встал в конец.

Пошаговый пример

Исходный массив:

[3, 6, 1, 5, 2, 4]

Находим максимум 6 и переворачиваем префикс до него → [6, 3, 1, 5, 2, 4]
Переворачиваем весь массив → [4, 2, 5, 1, 3, 6]
Повторяем для оставшейся части массива

Псевдокод

size = n
while size > 1:
    max_index = argmax(arr[0...size])
    if max_index != size - 1:
        if max_index != 0:
            flip(arr, max_index)
        flip(arr, size - 1)
    size -= 1

Оптимизация: Минимизация числа переворотов — отдельная исследовательская задача.

Сложность

Время O(n²) в количестве сравнений и переворотов.

Память O(1), in-place.

Когда используется

Задачи, где разрешена только операция переворота
Обучение нестандартным операциям
Спортивное программирование

Ключевые свойства

Не стабильный
In-place
Использует только операцию flip

Pancake Sort

Pancake Sort Visualizer

Pancake Sort

Основная идея

Пошаговый пример

Псевдокод

Сложность

Когда используется

Ключевые свойства

Комментарии к уроку