In der AP2 kommt oft: „Wie sieht die Liste nach dem 2. Durchlauf aus?“ Dafür musst du wissen, was ein Durchlauf beim jeweiligen Verfahren ist. Beispiel: die Liste 5, 2, 8, 1, 9 aufsteigend sortieren.
Bubblesort
Benachbarte Zahlen vergleichen und tauschen, wenn die linke größer ist. Nach jedem Durchlauf steht die größte Zahl des unsortierten Teils ganz hinten.
Durchlauf
Liste
Start
5, 2, 8, 1, 9
1.
2, 5, 1, 8, 9
2.
2, 1, 5, 8, 9
Selectionsort
Die kleinste Zahl im unsortierten Teil suchen und mit der ersten Zahl dieses Teils tauschen. Pro Durchlauf höchstens ein Tausch.
Durchlauf
Liste
Start
5, 2, 8, 1, 9
1.
1, 2, 8, 5, 9
2.
1, 2, 8, 5, 9 (2 stand schon richtig)
Insertionsort
Die nächste Zahl nehmen und links in den sortierten Teil einfügen, wie Spielkarten auf der Hand. Rechts davon ändert sich nichts.
Durchlauf
Liste
Start
5, 2, 8, 1, 9
1.
2, 5, 8, 1, 9
2.
2, 5, 8, 1, 9 (8 bleibt)
Eigenschaften
Verfahren
Laufzeit
stabil
in-place
Bubble
O(n²)
ja
ja
Selection
O(n²)
nein
ja
Insertion
O(n²)
ja
ja
Merge
O(n log n)
ja
nein
Quick
O(n²)*
nein
ja
Laufzeit im schlechtesten Fall. *Quicksort braucht im Mittel nur O(n log n). Insertionsort ist bei fast sortierten Listen O(n), Selectionsort braucht immer O(n²) Vergleiche.
Bubblesort ohne Abbruch braucht n − 1 Durchläufe und n · (n − 1) / 2 Vergleiche.
Typische Fehler
Bei Insertionsort zählt das Einfügen der zweiten Zahl als 1. Durchlauf.
Bei Selectionsort nicht benachbart tauschen, sondern das Minimum direkt nach vorne.
Bei Bubblesort im 2. Durchlauf nicht mehr bis ganz hinten vergleichen: Die letzte Zahl ist schon sortiert.
Beispielaufgabe mit Lösung
Selectionsort: Liste nach 1. Durchlauf
Die Liste 66, 62, 16, 22, 68, 80 wird mit Selectionsort aufsteigend sortiert. Ein Durchlauf sucht die kleinste Zahl im unsortierten Teil und vertauscht sie mit der ersten Zahl dieses Teils.
Wie sieht die Liste nach dem 1. Durchlauf aus, und wie viele Vertauschungen gab es in diesem Durchlauf?
Lösung anzeigen
Liste nach dem 1. Durchlauf:16, 62, 66, 22, 68, 80
Vertauschungen im 1. Durchlauf:1
Lösungsweg
Start: 66, 62, 16, 22, 68, 80
Nach 1. Durchlauf: 16, 62, 66, 22, 68, 80 (kleinste Zahl 16 wird mit 66 getauscht; 1 Vertauschungen)
Selectionsort tauscht pro Durchlauf höchstens einmal.
Oben bekommst du jedes Mal eine neue Aufgabe dieser Art, mit Lösungsweg.
Weitere Themen
Oder gemischt üben: jede Aufgabe aus einem anderen Thema.