Maximum finden
Durchsuche den noch unsortierten Bereich. Merke dir den Index seiner größten Zahl.
ALGORITHMEN VERSTEHEN / PANCAKE SORT
Ein Stapel. Eine Operation.
Nur den oberen Teil wenden – bis alle Zahlen aufsteigend sortiert sind.
DEIN EXPERIMENT
Bring Ordnung rein.
Die Regel
Ein Flip kehrt ein Präfix um: die ersten k Elemente. Der fertige Bereich unten bleibt unberührt.
LIVE-STAPEL Index 0 obenStart
Finde die größte Zahl im unsortierten Bereich.
02 / DER ALGORITHMUS
Erst nach oben. Dann an seinen Platz.
Zweimal wenden
Wende bis zum Maximum, damit es oben liegt. Wende danach den gesamten unsortierten Bereich.
Bereich verkleinern
Das Maximum liegt jetzt richtig. Wiederhole alles für eine Zahl weniger.
Der unten gemessene Algorithmus ist genau dieser JavaScript-Code. Die Animation ergänzt separate Erklärungsschritte.
03 / THEORIE TRIFFT MESSUNG
Doppelte Menge. Vierfache Zeit?
Vergleiche n und 2n eindeutige Werte unter denselben Bedingungen.
Bereit. Gemessen wird nur das Sortieren – ohne Animation und Datenerzeugung.
Nach Aufwärmläufen folgen sieben Messungen je Datenmenge. Browser, JIT und Hintergrundlast beeinflussen die Zeit. Ein einzelner Vergleich beweist keine Komplexitätsklasse.
04 / FÜR DEINEN VORTRAG
Was du erklären können solltest.
Beide Θ(n²)
Die gezeigte Variante sucht in jedem Durchlauf das Maximum: (n−1) + … + 1 = n(n−1)/2 Vergleiche, unabhängig von der Reihenfolge.
Best Case: aufsteigend, keine Flips. Auch dann bleiben alle Vergleiche. Worst Case: Θ(n²) inklusive Wendungen. Umgekehrt sortiert ist hier kein Worst-Case-Beispiel: Ein Flip kann genügen.
Eine zusätzliche Prüfung „schon sortiert?“ könnte den Best Case auf Θ(n) senken. Dieser Code enthält sie bewusst nicht.
O(1) zusätzlich
Die iterative Sortierung tauscht Werte direkt im Eingabearray. Sie braucht nur eine feste Anzahl Variablen, keinen Rekursionsstapel.
Die Eingabe selbst benötigt O(n) Speicher. Kopien, Visualisierung und Testdaten der Website kommen zusätzlich dazu; sie gehören nicht zum Hilfsspeicher des Sortierkerns.
Nicht stabil
Gleiche Schlüssel behalten ihre ursprüngliche Reihenfolge nicht zwingend. Ein Präfix-Flip kann sie vertauschen.
Gedankliches Beispiel: [2ₐ, 2ᵦ, 1] wird mit dieser Variante zu [1, 2ᵦ, 2ₐ]. A und B sind vertauscht.
Nur dieses Erklärbeispiel verwendet gleiche Schlüssel. Demo und Messungen akzeptieren ausschließlich eindeutige Werte.
Ein Problem von 1975
Jacob E. Goodman veröffentlichte das Pancake-Problem unter dem Pseudonym „Harry Dweighter“. Die Idee: Ein Kellner sortiert Pfannkuchen nur mit einem Pfannenwender.
1979 untersuchten William H. Gates und Christos H. Papadimitriou Schranken für Präfix-Wendungen. Die hier gezeigte einfache Greedy-Methode sucht keine minimale Flipfolge.
Lehre & Forschung
Pancake Sort macht Greedy-Strategien, Invarianten und eingeschränkte Operationen anschaulich.
In der Forschung modellieren Pancake-Netzwerke Permutationen als Knoten und Präfix-Wendungen als Verbindungen. Eine Sortierfolge beschreibt dort einen Routingweg.
Kein typischer Ersatz für effiziente Standardsortierung in Alltagssoftware.
Die Invariante ist der Schlüssel.
„Nach jedem Durchlauf liegt die größte noch unsortierte Zahl an ihrer endgültigen Position. Der fertige Bereich wächst von unten nach oben.“
Zeige einen Durchlauf, erläutere die zwei Flips und die kleiner werdende Schleife. Starte anschließend die Messung: Bei Θ(n²) erwarten wir T(2n)/T(n) ≈ 4.
Quellen zum WeiterlesenDouglas B. West · The Pancake ProblemsGates & Papadimitriou · Originalarbeit (1979)Komplexität und Speicherbedarf sind direkt am gezeigten Code hergeleitet.