algorithm
Масленица

Основная информация о Pancake

Масленица - это разговорный термин для математической проблемы сортировки неупорядоченной стопки блинов в порядке размера, когда шпатель может быть вставлен в любую точку стека и используется, чтобы перевернуть все блины над ним. Число блинов - это минимальное количество флип, необходимых для данного количества блинов.

В отличие от традиционного алгоритма сортировки, который пытается сортировать с наименьшим количеством сравнений, цель состоит в том, чтобы отсортировать последовательность как можно меньше разворотов.

Идея состоит в том, чтобы сделать что-то похожее на Selection Sort. Мы по одному помещаем максимальный элемент в конце и уменьшаем размер текущего массива на единицу.

Расселение проблемы:

1. Необходимо заказать блины от самых маленьких (сверху) до самых больших (внизу), стартовый стек можно организовать в любом порядке.
2. Я могу выполнять флип, переворачивая весь стек.
3. Чтобы перевернуть конкретный блины на дно стека, сначала нужно перевернуть его вверх (затем перевернуть его на дно).
4. Чтобы заказать каждый блин, потребуется один флип вверх и один флип вниз до его окончательного местоположения.

Интуитивный алгоритм:

1. Найдите самый крупный блайнд и переверните его на дно (вам может потребоваться сначала перевернуть его в верхнюю часть стека).

2. Повторите шаг 1 до тех пор, пока не будет упорядочен стек.

3. Вот и все, двухэтапный алгоритм будет работать.

Пример алгоритма сортировки блинов:

Вспомогательное пространство: O(1)
Сложность времени: O(n^2)

Реализация C #

public class PancakeSort
{
    private static void SortPancake(int[] input, int n)
    {
        for (var bottom = n - 1; bottom > 0; bottom--)
        {
            var index = bottom;
            var maxIndex = input[bottom];
            int i;
            for (i = bottom - 1; i >= 0; i--)
            {
                if (input[i] > maxIndex)
                {
                    maxIndex = input[i];
                    index = i;
                }
            }
            if (index == bottom) continue;
            var temp = new int[n];
            var j = 0;
            for (i = bottom; i > index; i--,j++)
            {
                temp[j] = input[i];
            }
            for (i = 0; i < index; i++, j++)
            {
                temp[j] = input[i];
            }
            if (temp.Length > j) temp[j] = input[index];
            for (i = 0; i <= bottom; i++)
            {
                input[i] = temp[i];
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortPancake(input, input.Length);
        return input;
    }
}