Algorithmen sichtbar gemacht
Algorithmen sichtbar gemacht ist eine kostenlose interaktive Simulation aus dem StudyFi Lab. Sie läuft direkt im Browser, ohne Anmeldung und ohne Installation.
Sortieren und Suchen, Schritt für Schritt
Experimente
Bubblesort
Bubblesort vergleicht benachbarte Elemente und vertauscht sie, wenn sie falsch herum stehen. Nach jedem Durchlauf ist das größte Element ans Ende „aufgestiegen“, der unsortierte Teil wird also kürzer. Gibt es in einem Durchlauf keine Vertauschung, ist das Array sortiert. Im schlechtesten Fall braucht es n(n−1)/2 Vergleiche, also O(n²).
Probier das: Wähle eine umgekehrte Eingabe und vergleiche die Zahl der Vergleiche mit n(n−1)/2. Probiere dann ein fast sortiertes Array — es endet nach wenigen Durchläufen.
Insertionsort
Insertionsort funktioniert wie das Sortieren von Spielkarten in der Hand: Der linke Teil ist schon sortiert, und jedes nächste Element (key) wandert nach links, bis es auf ein kleineres trifft. Größere Elemente rücken dabei eine Stelle nach rechts. Bei zufälligen Daten ist das O(n²), bei fast sortierten fast O(n) — ein sortiertes Array braucht nur n−1 Vergleiche.
Probier das: Lass es auf einem fast sortierten und dann auf einem umgekehrten Array laufen. Wie viel mehr Verschiebungen braucht das umgekehrte?
Mergesort
Mergesort teilt das Array in zwei Hälften, sortiert jede auf dieselbe Weise (Rekursion) und verschmilzt dann die beiden sortierten Hälften: Es nimmt immer das kleinere der beiden vorderen Elemente. Das Halbieren ergibt log₂ n Ebenen, und jede Ebene verarbeitet alle n Elemente, die Laufzeit ist also immer O(n log n). Bei Gleichstand nimmt es das linke Element, deshalb ist es stabil.
Probier das: Probiere ein umgekehrtes und dann ein fast sortiertes Array gleicher Größe. Die Zahl der Vergleiche ändert sich kaum — die Reihenfolge der Eingabe spielt fast keine Rolle.
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²).
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.
Lineare vs. binäre Suche
Die lineare Suche prüft die Elemente eins nach dem anderen und braucht im schlechtesten Fall n Schritte — O(n). Die binäre Suche funktioniert nur auf einem sortierten Array: Sie schaut in die Mitte und verwirft je nach Ergebnis eine ganze Hälfte. Nach jedem Schritt bleibt höchstens die Hälfte übrig, daher genügen höchstens ⌈log₂(n+1)⌉ Schritte — O(log n). Bei 40 Elementen sind das 6 Schritte statt 40.
Probier das: Stelle 40 Elemente ein und suche den letzten Wert. Wähle dann eine Zahl, die nicht im Array steht — wie viele Schritte braucht jede Suche, um das festzustellen?
Sortier-Wettrennen
Alle vier Algorithmen sortieren dieselbe Eingabe, und in jeder Bahn ist ein Schritt ein Vergleich oder eine Bewegung. Die O(n²)-Verfahren (Bubblesort und Insertionsort) wachsen mit der Arraygröße viel schneller als die O(n log n)-Verfahren (Mergesort und Quicksort). Die Reihenfolge hängt aber auch von der Eingabe ab: Bei einem fast sortierten Array gewinnt oft Insertionsort.
Probier das: Starte das Rennen mit einem zufälligen Array aus 40 Elementen und wechsle dann zu fast sortiert. Ändert sich der Sieger?
Häufige Fragen
Was ist Algorithmen sichtbar gemacht?
Algorithmen sichtbar gemacht ist eine kostenlose interaktive Simulation aus dem StudyFi Lab. Sie läuft direkt im Browser, ohne Anmeldung und ohne Installation. Sortieren und Suchen, Schritt für Schritt
Ist Algorithmen sichtbar gemacht kostenlos?
Ja. Algorithmen sichtbar gemacht ist komplett kostenlos. Es läuft im Browser auf Computer, Tablet und Handy, und du brauchst kein Konto.
Was kann ich in Algorithmen sichtbar gemacht entdecken?
Bubblesort, Insertionsort, Mergesort, Quicksort, Lineare vs. binäre Suche, Sortier-Wettrennen.
Was zeigt das Experiment „Bubblesort“?
Bubblesort vergleicht benachbarte Elemente und vertauscht sie, wenn sie falsch herum stehen. Nach jedem Durchlauf ist das größte Element ans Ende „aufgestiegen“, der unsortierte Teil wird also kürzer. Gibt es in einem Durchlauf keine Vertauschung, ist das Array sortiert. Im schlechtesten Fall braucht es n(n−1)/2 Vergleiche, also O(n²).
Was zeigt das Experiment „Insertionsort“?
Insertionsort funktioniert wie das Sortieren von Spielkarten in der Hand: Der linke Teil ist schon sortiert, und jedes nächste Element (key) wandert nach links, bis es auf ein kleineres trifft. Größere Elemente rücken dabei eine Stelle nach rechts. Bei zufälligen Daten ist das O(n²), bei fast sortierten fast O(n) — ein sortiertes Array braucht nur n−1 Vergleiche.
Lernst du für eine Prüfung?
Lade deine Notizen hoch und StudyFi macht daraus Karteikarten, Tests und Podcasts.