algorithm
Ordine di frittella

Pancake Ordina informazioni di base

Pancake Sort è un termine colloquiale per il problema matematico di ordinare una pila disordinata di pancake in ordine di grandezza quando una spatola può essere inserita in qualsiasi punto della pila e utilizzata per capovolgere tutti i pancake sopra di essa. Un numero di pancake è il numero minimo di lanci necessari per un determinato numero di pancake.

A differenza di un algoritmo di ordinamento tradizionale, che tenta di ordinare con il minor numero possibile di confronti, l'obiettivo è di ordinare la sequenza nel minor numero possibile di inversioni.

L'idea è di fare qualcosa di simile a Selection Sort. Noi uno alla volta posizioniamo l'elemento massimo alla fine e riduciamo la dimensione dell'array attuale di uno.

Sezionare il problema:

1. È necessario ordinare i pancake dal più piccolo (in alto) al più grande (in basso), la pila iniziale può essere disposta in qualsiasi ordine.
2. Posso solo eseguire flip capovolgere l'intero stack.
3. Per capovolgere un pancake specifico nella parte inferiore della pila, dobbiamo prima capovolgerlo in alto (quindi ruotarlo nuovamente verso il basso).
4. Per ordinare ogni pancake sarà necessario un flip up in alto e uno flip down nella sua posizione finale.

Algoritmo intuitivo:

1. Trova il pancake fuori ordine più grande e giralo verso il basso (potresti doverlo prima girare in cima alla pila).

2. Ripeti il ​​passaggio uno finché non viene ordinato lo stack.

3. Questo è tutto, un algoritmo in due fasi funzionerà.

Esempio di algoritmo di ordinamento Pancake:

Spazio ausiliario: O(1)
Complessità del tempo: O(n^2)

Implementazione 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;
    }
}