algorithm
Pannenkoeken sorteren

Pannenkoeken Sorteren Basisinformatie

Pannenkoeken sorteren is een begrip in de omgangstaal voor het wiskundige probleem van het sorteren van een ongeordende stapel pannenkoeken in volgorde van grootte wanneer een spatel op een willekeurig punt in de stapel kan worden geplaatst en gebruikt om alle pannenkoeken erboven om te draaien. Een aantal pannenkoeken is het minimum aantal flips dat nodig is voor een bepaald aantal pannenkoeken.

In tegenstelling tot een traditioneel sorteeralgoritme, dat probeert te sorteren met zo min mogelijk vergelijkingen, is het doel om de reeks in zo min mogelijk omkeringen te sorteren.

Het idee is om iets vergelijkbaars te doen met Selectie sorteren. We plaatsen één voor één maximaal element aan het einde en verkleinen de huidige array met één.

Het probleem ontleden:

1. Noodzaak om de pannenkoeken te bestellen van kleinste (boven) tot grootste (onder), de startstapel kan in elke volgorde worden gerangschikt.
2. Ik kan alleen de hele stapel omdraaien.
3. Om een specifieke pannenkoek naar de onderkant van de stapel te draaien, moeten we deze eerst naar de bovenkant draaien (en vervolgens weer naar de onderkant draaien).
4. Om elke pannenkoek te bestellen, heeft u één klep naar boven en één klep naar beneden nodig.

Intuïtief algoritme:

1. Zoek de grootste buiten gebruik zijnde pannenkoek en draai deze naar beneden (mogelijk moet je deze eerst naar de bovenkant van de stapel omdraaien).

2. Herhaal stap één totdat de stapel is besteld.

3. Dat is alles, een tweestaps algoritme zal werken.

Voorbeeld van Pancake-sorteeralgoritme:

Hulpruimte: O(1)
Tijd Complexiteit: O(n^2)

C # Implementatie

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