Bubblesort, Insertionsort, Mergesort, Quicksort und Heapsort auf derselben Permutation — fünf Balkenreihen schreiten synchron.
Zum Modell
Fünf vergleichsbasierte Sortieralgorithmen arbeiten auf derselben Permutation der Zahlen 1…n: Bubblesort (Vertauschen von Nachbarn), Insertionsort (Zurückschieben des Schlüssels), Mergesort von unten nach oben (Durchläufe mit verdoppelter Breite), Quicksort mit Lomuto-Partition und explizitem Intervallstapel, Heapsort (Aufbau eines Max-Heaps und Einsickern beim Entnehmen). Ein gemeinsamer Mikroschritt bewegt alle fünf zugleich: man sieht verschiedene Vertauschungsbilder, keinen Wettlauf nach Prozessorzeit — die Verfahren brauchen unterschiedlich viele Schritte. Die Balken sind nach dem ursprünglichen Index gefärbt; die Hervorhebung markiert den aktuellen Vergleich oder Tausch. Das ist eine Lehranimation von Vergleichen und Vertauschungen, keine Messung der realen Laufzeit auf einer konkreten Maschine.
Für wen: Einführende Informatik: Vergleich der Familien O(n²) und O(n log n) auf derselben Permutation.
Wichtige Begriffe
bubblesort
insertionsort
mergesort
quicksort
heapsort
lomuto-partition
binärer heap
stabilität der sortierung
So funktioniert es
Eine Permutation 1…n, fünf Sortierverfahren. Jeder Mikroschritt — Vergleich oder Tausch — läuft in allen Reihen zugleich, daher sieht man, wie sich das Feld bei Bubblesort, Insertionsort, Mergesort von unten, Quicksort (Lomuto) und Heapsort verschieden umordnet, und nicht nur, wer nach der Uhr schneller ist.
Häufige Fragen
Warum enden die Reihen zu verschiedenen Zeiten?
Bei derselben Eingabe brauchen die Algorithmen verschieden viele Vergleiche und Vertauschungen. Der gemeinsame Schritt gilt trotzdem für alle fünf: bereits sortierte Reihen stehen, bis die „längeren“ nach der Zahl der Operationen aufholen.
Ist Mergesort hier stabil?
Bei gleichen Schlüsseln nimmt das Mischen das Element aus der linken Hälfte (Bedingung ≤) — die übliche stabile Umsetzung. Die übrigen gezeigten Verfahren garantieren Stabilität im Allgemeinen nicht.
Warum wirkt Quicksort unruhiger als Heapsort?
Die Lomuto-Partition durchläuft das Teilfeld und tauscht oft um das Pivotelement; bei Heapsort liegt die Arbeit im Einsickern längs eines Pfades im Baum. Die Ordnung O(n log n) im typischen Fall gilt für beide, Konstanten und Bewegungsmuster sind verschieden.