algorithm
Sortuj naleśniki

Podstawowe informacje na temat sortowania naleśników

Sortowanie naleśników jest potocznym określeniem matematycznego problemu sortowania nieuporządkowanego stosu naleśników według wielkości, gdy szpachelka może być włożona w dowolnym punkcie stosu i używana do przewracania wszystkich naleśników nad nim. Liczba naleśników to minimalna liczba przewrotek wymagana dla danej liczby naleśników.

W przeciwieństwie do tradycyjnego algorytmu sortowania, który próbuje sortować przy możliwie najmniejszej liczbie porównań, celem jest posortowanie sekwencji w jak najmniejszej liczbie odwróceń.

Chodzi o to, aby zrobić coś podobnego do Sortowania selekcji. Jeden po drugim umieszczamy maksymalny element na końcu i zmniejszamy rozmiar bieżącej tablicy o jeden.

Analiza problemu:

1. Konieczność zamówienia naleśników od najmniejszej (górnej) do największej (dolnej), stos początkowy można ułożyć w dowolnej kolejności.
2. Mogę tylko wykonać przerzucenie całego stosu.
3. Aby przerzucić konkretny naleśnik na spód stosu, musimy najpierw przewrócić go na górę (a następnie ponownie na dół).
4. Aby zamówić każdy naleśnik, konieczne będzie jedno przewrócenie w górę i jedno przewrócenie w dół do jego ostatecznego położenia.

Intuicyjny algorytm:

1. Znajdź największy niedziałający naleśnik i przewróć go na dół (być może najpierw będziesz musiał przerzucić go na górę stosu).

2. Powtarzaj krok pierwszy, aż stos zostanie uporządkowany.

3. To wszystko, algorytm dwuetapowy będzie działał.

Przykład algorytmu sortowania Pancake:

Przestrzeń pomocnicza: O(1)
Złożoność czasu: O(n^2)

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