Блинная сортировка (Pancake Sort)

Блинная сортировка (Pancake Sort) — это неэффективный, но интересный способ сортировки массива, который использует операции "переворота" (flip). Он получил свое название благодаря аналогии с переворачиванием блинов на сковороде. Основная идея заключается в том, что мы можем "перевернуть" часть массива, чтобы переместить максимальный элемент в нужную позицию.

▎Основные шаги алгоритма:

1. Нахождение максимального элемента: Находим индекс максимального элемента в текущем неотсортированном массиве.

2. Переворот до максимального элемента: Если максимальный элемент не находится на своем месте, мы переворачиваем массив от начала до индекса максимального элемента. Это помещает максимальный элемент на первую позицию.

3. Переворот до конца: Затем мы переворачиваем массив от начала до последнего элемента (неотсортированной части). Это помещает максимальный элемент на его окончательную позицию в отсортированном массиве.

4. Повторение: Повторяем шаги 1-3 для оставшейся части массива (исключая последний элемент, который уже отсортирован).

▎Временная сложность:

1. Лучший случай: O(n) — если массив уже отсортирован, алгоритм может завершиться быстрее, так как будет выполнять меньше переворотов.

2. Средний случай: O(n²) — в среднем, алгоритм требует порядка n итераций для нахождения максимального элемента в неотсортированной части массива, и для каждой итерации может потребоваться до n переворотов.

3. Худший случай: O(n²) — в худшем случае, когда элементы находятся в обратном порядке, алгоритму потребуется максимальное количество переворотов для сортировки.

▎Пространственная сложность:

• Пространственная сложность: O(1) — алгоритм выполняется "на месте" и не требует дополнительной памяти для хранения данных, кроме переменных, используемых для управления циклом и временных переменных для переворотов.

▎Устойчивость:

Данный алгоритм сортировки не является устойчивым, это означает, что при сортировке элементов с одинаковыми ключами их относительный порядок не сохраняется. То есть, если два элемента имеют одинаковое значение и один из них идет перед другим в исходном массиве, то после сортировки первый элемент не обязательно останется перед вторым.

Реализация алгоритма на C++:

Реализация алгоритма на Python: