Bubblesort
Bubblesort ist ein interaktives Experiment in Algorithmen sichtbar gemacht, einer kostenlosen Simulation aus dem StudyFi Lab, die direkt im Browser läuft.
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.
Häufige Fragen
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²).
Wie probiere ich „Bubblesort“ aus?
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.
Lernst du für eine Prüfung?
Lade deine Notizen hoch und StudyFi macht daraus Karteikarten, Tests und Podcasts.