algorithm
Tipo de panqueque

Información básica sobre el tipo de panqueque

Pancake Sort es un término coloquial para el problema matemático de clasificar una pila desordenada de pancakes en orden de tamaño cuando se puede insertar una espátula en cualquier punto de la pila y se usa para voltear todas las pancakes por encima. Un número de panqueques es el número mínimo de tirones requeridos para un número dado de panqueques.

A diferencia de un algoritmo de clasificación tradicional, que intenta clasificar con la menor cantidad de comparaciones posible, el objetivo es clasificar la secuencia en la menor cantidad de inversiones posible.

La idea es hacer algo similar a la selección por selección. Colocamos el elemento máximo uno por uno al final y reducimos el tamaño de la matriz actual en uno.

Diseccionando el problema:

1. Si necesita ordenar los panqueques de la más pequeña (superior) a la mayor (inferior), la pila de inicio se puede organizar en cualquier orden.
2. Solo puedo realizar voltear todo el stack.
3. Para voltear un panqueque específico a la parte inferior de la pila, primero debemos voltearlo a la parte superior (luego voltearlo nuevamente a la parte inferior).
4. Para ordenar cada panqueque se requerirá un giro hacia arriba y otro hacia abajo hasta su ubicación final.

Algoritmo intuitivo:

1. Encuentre el panqueque más grande que esté fuera de orden y colóquelo en la parte inferior (es posible que primero tenga que voltearlo hacia la parte superior de la pila).

2. Repita el paso uno hasta que se ordene la pila.

3. Eso es todo, un algoritmo de dos pasos funcionará.

Ejemplo de algoritmo de clasificación de panqueques:

Espacio auxiliar: O(1)
Complejidad del tiempo: O(n^2)

Implementación de 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;
    }
}