Quicksort
Quicksort ist ein interaktives Experiment in Algorithmen sichtbar gemacht, einer kostenlosen Simulation aus dem StudyFi Lab, die direkt im Browser läuft.
Quicksort wählt ein Pivotelement — hier das letzte Element des Bereichs (Lomuto-Partitionierung) — und ordnet den Bereich so um, dass kleinere Elemente links und die übrigen rechts stehen. Das Pivot steht danach an seinem endgültigen Platz, und beide Teile werden genauso sortiert. Im Mittel ist das O(n log n), teilt das Pivot aber schlecht (etwa bei einem schon sortierten oder umgekehrten Array), wird es O(n²).
Probier das: Vergleiche eine zufällige mit einer umgekehrten Eingabe. Beim umgekehrten Array ist das Pivot immer das größte oder kleinste — sieh, wie die Vergleiche hochschnellen.
Häufige Fragen
Was zeigt das Experiment „Quicksort“?
Quicksort wählt ein Pivotelement — hier das letzte Element des Bereichs (Lomuto-Partitionierung) — und ordnet den Bereich so um, dass kleinere Elemente links und die übrigen rechts stehen. Das Pivot steht danach an seinem endgültigen Platz, und beide Teile werden genauso sortiert. Im Mittel ist das O(n log n), teilt das Pivot aber schlecht (etwa bei einem schon sortierten oder umgekehrten Array), wird es O(n²).
Wie probiere ich „Quicksort“ aus?
Vergleiche eine zufällige mit einer umgekehrten Eingabe. Beim umgekehrten Array ist das Pivot immer das größte oder kleinste — sieh, wie die Vergleiche hochschnellen.
Lernst du für eine Prüfung?
Lade deine Notizen hoch und StudyFi macht daraus Karteikarten, Tests und Podcasts.