algorithm
Pfannkuchen Sort

Pfannkuchen sortieren grundlegende Informationen

Pancake Sort ist der umgangssprachliche Ausdruck für das mathematische Problem des Sortierens eines ungeordneten Stapels von Pfannkuchen in der Reihenfolge seiner Größe, wenn ein Spatel an einer beliebigen Stelle des Stapels eingefügt werden kann, um alle darüber liegenden Pfannkuchen zu wenden. Eine Pfannkuchenanzahl ist die Mindestanzahl von Flips, die für eine bestimmte Anzahl von Pfannkuchen erforderlich ist.

Im Gegensatz zu einem herkömmlichen Sortieralgorithmus, der versucht, mit möglichst wenigen Vergleichen zu sortieren, besteht das Ziel darin, die Reihenfolge in möglichst wenigen Umkehrungen zu sortieren.

Die Idee ist, etwas Ähnliches wie Selection Sort zu tun. Wir setzen nacheinander das maximale Element ein und reduzieren die Größe des aktuellen Arrays um eins.

Das Problem analysieren:

1. Die Pfannkuchen müssen von kleinster (oberer) bis größter (unterer) bestellt werden. Der Startstapel kann in beliebiger Reihenfolge angeordnet werden.
2. Ich kann nur den gesamten Stapel umdrehen.
3. Um einen bestimmten Pfannkuchen an den unteren Rand des Stapels zu kippen, müssen wir ihn zuerst nach oben drehen (dann wieder nach unten).
4. Um jeden Pfannkuchen zu bestellen, benötigen Sie eine Wende nach oben und eine Wende bis zum endgültigen Ort.

Intuitiver Algorithmus:

1. Finden Sie den größten Pfannkuchen außerhalb der Reihenfolge und drehen Sie ihn nach unten (möglicherweise müssen Sie ihn zuerst auf den Stapel legen).

2. Wiederholen Sie Schritt 1, bis der Stapel bestellt ist.

3. Ein zweistufiger Algorithmus wird funktionieren.

Beispiel für einen Pancake-Sortieralgorithmus:

Hilfsraum: O(1)
Zeitkomplexität: O(n^2)

C # -Implementierung

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