Zum Inhalt
Alle Apps

Quicksort

Über diese App

Quicksort Schritt für Schritt — Pivot-Wahl, Partitionierung und Tauschoperationen interaktiv nachvollziehen.

Wie Quicksort sortiert

Quicksort folgt dem Prinzip Teile und herrsche. Aus einem Abschnitt des Arrays wird ein Pivot-Element gewählt, hier wie bei der Lomuto-Partition das letzte Element. Ein Zeiger läuft durch den Abschnitt, vergleicht jedes Element mit dem Pivot und tauscht kleinere oder gleiche Werte nach vorne. Am Ende rückt das Pivot genau zwischen die beiden Teile und steht damit an seiner endgültigen Position. Danach wird derselbe Vorgang rekursiv auf den linken und den rechten Teil angewendet. Im Mittel braucht Quicksort O(n log n) Vergleiche, im ungünstigsten Fall, etwa bei bereits sortierten Daten mit diesem Pivot, O(n²).

Was die App zeigt

Jeder Schritt erscheint als eigene Zeile: Pivot-Wahl, Vergleich, Tausch und Platzierung. Farben unterscheiden das Pivot, das gerade verglichene Element, die beiden Partitionen und die bereits endgültig sortierte Region. Eine farbige Leiste am Rand zeigt die Rekursionstiefe, ein Zähler die Position im Ablauf. So wird sichtbar, dass jedes platzierte Pivot nie wieder angefasst wird.

Selbst ausprobieren

Gib eigene Zahlen ein (2 bis 16 Werte) oder lass ein zufälliges Array mischen. Mit Vorwärts und Zurück gehst du Schritt für Schritt durch die Partitionierung, springst an den Anfang oder ans Ende oder lässt den Ablauf automatisch in wählbarem Tempo abspielen. Probier ein bereits sortiertes Array aus und zähle, wie viele Schritte es braucht.

Häufige Fragen

Was ist das Pivot-Element bei Quicksort?
Das Pivot ist der Vergleichswert, an dem ein Abschnitt aufgeteilt wird: Alle kleineren oder gleichen Elemente kommen nach links, alle größeren nach rechts. Nach der Partitionierung steht das Pivot an seiner endgültigen Position im sortierten Array. Bei der Lomuto-Partition ist das Pivot das letzte Element des Abschnitts.
Welche Laufzeit hat Quicksort?
Im Mittel O(n log n), weil das Pivot den Abschnitt meist grob halbiert und die Rekursion etwa log n Ebenen tief wird. Im schlechtesten Fall O(n²): Wenn das Pivot immer das größte oder kleinste Element ist, etwa bei einem schon sortierten Array und dem letzten Element als Pivot, schrumpft jeder Abschnitt nur um eins.
Ist Quicksort stabil?
Nein. Beim Tauschen können gleiche Werte ihre ursprüngliche Reihenfolge verlieren. Quicksort sortiert dafür in place, braucht also außer dem Rekursionsstapel keinen zusätzlichen Speicher.
Was kann ich in der Quicksort-App ausprobieren?
Du gibst eigene Zahlen ein oder mischst zufällig, gehst jeden Vergleich und Tausch einzeln durch, spulst zurück oder lässt den Ablauf abspielen. Farben markieren Pivot, Vergleich, Partitionen und sortierte Bereiche, eine Leiste zeigt die Rekursionstiefe.

Fach: Informatik

Mehr aus Informatik

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps