Arbeitsblatt Sortieralgorithmen
Lösung geprüft
Die Aufgabe der heutigen Stunde ist das Arbeitsblatt zu Sortieralgorithmen! Hier wird es einmal andersherum: statt einen Algorithmus anzuwenden, sollst du aus den Zwischenschritten erkennen, welcher es war. Das ist eine typische Klausurfrage.
1 Einzelarbeit In Material 1 finden Sie eine Schritt-für-Schritt-Durchführung eines Ihnen bekannten Sortieralgorithmus. Begründen Sie, um welches Sortierverfahren es sich handelt.
2 Einzelarbeit Nutzen Sie den von Ihnen oben identifizierten Algorithmus, um die Zahlenfolge in Material 2 Schritt-für-Schritt zu sortieren.
3 Partnerarbeit Vergleichen Sie mit Ihrem Sitznachbarn die Tabellen und prüfen Sie, ob die Schritte übereinstimmen. Um den Fehler zu identifizieren, markieren Sie die Stellen, die nicht übereinstimmen und erörtern Sie, wieso es zum Fehler kam.
4 Einzelarbeit Definieren Sie eine Zahlenfolge bestehend aus sechs Zahlen zwischen 0 und 100, die Ihr Sitznachbar sortieren soll. Tragen Sie die Zahlenfolge in Material 3 ein.
5 Partnerarbeit Sortieren Sie die Zahlenfolge Ihres Sitznachbarn. Falls es zu Problemen kommen sollte, gehen Sie gemeinsam auf Fehlersuche.
Aufgabe 1 – Welcher Algorithmus ist das?
Material 1 zeigt das Array [57, 11, 93, 12, 44] und den
ersten Durchlauf in vier Einzelschritten:
Ausgangsarray [57, 11, 93, 12, 44]
Schritt 1 [11, 57, 93, 12, 44] 57 und 11 getauscht
Schritt 2 [11, 57, 93, 12, 44] 57 und 93 - kein Tausch
Schritt 3 [11, 57, 12, 93, 44] 93 und 12 getauscht
Schritt 4 [11, 57, 12, 44, 93] 93 und 44 getauschtDie Antwort: Bubble Sort
Drei Beobachtungen, die das zusammen belegen:
- Es werden immer nur direkte Nachbarn vertauscht. In Schritt 1 die Positionen 0 und 1, in Schritt 3 die Positionen 2 und 3. Nie springt ein Element über mehrere Plätze.
- Bei fünf Elementen gibt es pro Durchlauf genau vier Schritte – das sind die vier Nachbarpaare. Auch Schritt 2 ist ein Schritt, obwohl sich nichts ändert: es wurde verglichen und für richtig befunden.
- Am Ende des ersten Durchlaufs steht das größte Element (93) ganz rechts. Es ist von Position 2 über 3 nach 4 „geblubbert" – daher der Name.
Warum es die anderen beiden nicht sind
| Verfahren | Wie der erste Durchlauf aussähe | Passt? |
|---|---|---|
| Selection Sort | Es würde das Minimum (11) suchen und mit einem einzigen Tausch nach vorne holen: [11, 57, 93, 12, 44] und fertig. | nein – hier wird viermal verglichen und dreimal getauscht |
| Insertion Sort | Es würde Elemente verschieben, nicht tauschen, und der vordere Bereich wäre schon sortiert. | nein – 57 steht nach Schritt 4 immer noch vor der 12 |
| Bubble Sort | Nachbarn vergleichen, Größtes wandert nach hinten. | ja |
Der schnellste Test ist immer der letzte Punkt: schau, wo nach dem ersten Durchlauf das größte und wo das kleinste Element steht. Größtes hinten heißt Bubble Sort. Kleinstes vorne, sonst alles unverändert, heißt Selection Sort.
Aufgabe 2 – Material 2 sortieren
Ausgangsarray: [23, 22, 12, 44, 15], mit Bubble Sort. Jede
Zeile ist ein Vergleich zweier Nachbarn.
Erster Durchlauf Zweiter Durchlauf Dritter Durchlauf Vierter Durchlauf
Ausgangsarray [23,22,12,44,15] [22,12,23,15,44] [12,22,15,23,44] [12,15,22,23,44]
Einzelne [22,23,12,44,15] [12,22,23,15,44] [12,22,15,23,44] [12,15,22,23,44]
Schritte [22,12,23,44,15] [12,22,23,15,44] [12,15,22,23,44] [12,15,22,23,44]
[22,12,23,44,15] [12,22,15,23,44] [12,15,22,23,44] [12,15,22,23,44]
[22,12,23,15,44] [12,22,15,23,44] [12,15,22,23,44] [12,15,22,23,44]Was in den einzelnen Durchläufen passiert:
| Durchlauf | Getauscht | Ergebnis |
|---|---|---|
| 1 | 23↔22, 23↔12, 44↔15 | [22,12,23,15,44] – die 44 ist hinten angekommen |
| 2 | 22↔12, 23↔15 | [12,22,15,23,44] – die 23 sitzt fest |
| 3 | 22↔15 | [12,15,22,23,44] – fertig sortiert |
| 4 | nichts mehr | [12,15,22,23,44] |
Nach dem dritten Durchlauf ist die Folge bereits fertig. Der vierte läuft trotzdem, weil der einfache Bubble Sort stur seine n-1 Durchläufe macht. Genau das kann man optimieren: merkt man sich, ob in einem Durchlauf überhaupt getauscht wurde, kann man vorzeitig abbrechen.
Aufgaben 3 bis 5 – die Partnerarbeit
Diese drei Aufgaben macht man zu zweit, deshalb gibt es hier keine Musterlösung. Was sich lohnt, ist die typischen Fehlerquellen zu kennen – genau darum geht es in Aufgabe 3:
| Typischer Fehler | Woran man ihn erkennt |
|---|---|
| Schritte ohne Tausch weggelassen | Die Tabelle hat weniger als vier Zeilen pro Durchlauf |
| Nicht-Nachbarn vertauscht | Ein Element springt in einem Schritt über mehrere Plätze |
| Durchlauf zu früh abgebrochen | Das größte Element ist nach dem ersten Durchlauf nicht ganz hinten |
| Von rechts nach links verglichen | Statt des größten wandert das kleinste Element – das ist dann eine andere, aber auch gültige Variante |
Der letzte Punkt ist der, über den man sich mit dem Sitznachbarn am häufigsten streitet: Bubble Sort funktioniert in beide Richtungen. Solange ihr euch vorher einigt, welche Richtung ihr nehmt, sind beide Tabellen richtig – nur eben verschieden.
Für Aufgabe 4 sind sechs Zahlen gefordert. Ein Tipp: gib deinem
Sitznachbarn keine schon sortierte Folge, das ist langweilig. Eine
absteigend sortierte wie [91, 77, 60, 44, 23, 8] ist dagegen
der schlimmste Fall – da muss in jedem einzelnen Schritt getauscht werden,
fünf Durchläufe mit je fünf Vergleichen.