algorithm
Pannkakasortering

Pannkakasortering Grundläggande information

Pannkakasortering är en samhörighetsterm för det matematiska problemet med att sortera en ostörd pannkakestapel i storleksordning när en spatel kan placeras när som helst i bunten och användas för att vända alla pannkakor ovanför. Ett pannkakeantal är det minsta antalet vippor som krävs för ett givet antal pannkakor.

Till skillnad från en traditionell sorteringsalgoritm, som försöker sortera med så få jämförelser som möjligt, är målet att sortera sekvensen i så få reverseringar som möjligt.

Tanken är att göra något liknande Selection Sort. Vi placerar en efter en maximalt element i slutet och minskar storleken på strömmen med en.

Avlägsna problemet:

1. Behöver du beställa pannkakorna från minsta (övre) till största (botten), kan startbunten ordnas i valfri ordning.
2. Jag kan bara utföra vändning av hela stacken.
3. För att vända en specifik pannkaka till botten av bunten, måste vi först vända den till toppen (sedan vända den igen till botten).
4. För att beställa varje pannkaka krävs en vänd upp till toppen och en vänd ned till dess slutliga plats.

Intuitiv algoritm:

1. Hitta den största orubbliga pannkakan och vänd den till botten (du kan behöva vända den till toppen av bunten först).

2. Upprepa steg ett tills stacken har beställts.

3. Det är det, en tvåstegsalgoritm kommer att fungera.

Exempel på Pancake-sorteringsalgoritm:

Hjälprum: O(1)
Tidskomplexitet: O(n^2)

C # Implementering

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