Sortieralgorithmen üben

Prüfungsklassiker in Teil 2: Wie sieht die Liste nach einem Durchlauf aus, welches Verfahren war es, und wie viele Vergleiche braucht es?

Dieses Thema gehört zu Teil 2 der Abschlussprüfung (AP2), für AE und SI. Für die AP1 brauchst du es nicht.

Sortieralgorithmen

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

  1. Start: 66, 62, 16, 22, 68, 80
  2. Nach 1. Durchlauf: 16, 62, 66, 22, 68, 80 (kleinste Zahl 16 wird mit 66 getauscht; 1 Vertauschungen)
  3. Selectionsort tauscht pro Durchlauf höchstens einmal.

Oben bekommst du jedes Mal eine neue Aufgabe dieser Art, mit Lösungsweg.