Selection Sort Übungen
Hier können Sie Selection Sort direkt im Browser üben – ohne Arbeitsblatt, mit sofortiger Rückmeldung. Wie der Algorithmus funktioniert, steht auf der Seite Selection Sort. Zur Erinnerung: Selection Sort vergleicht das erste Element des noch unsortierten Bereichs nacheinander mit allen Elementen dahinter. Ist eines davon kleiner, werden die beiden sofort getauscht.
Die Positionen im Array zählen wir ab 0: Das erste Element ist array[0]. Bei den meisten Übungen gibt es den Knopf »Neue Werte« bzw. »Nächste Aufgabe« – Sie können also so lange üben, wie Sie möchten. Gespeichert wird nichts.
Der Kleinste-Zahl-an-den-Anfang-Algorithmus
(1) Schritt für Schritt: Die kleinste Zahl nach vorne bringen
Verglichen wird immer lottozahlen[0] mit einem Element dahinter. Entscheiden Sie bei jedem Vergleich: tauschen oder nicht? Am Ende muss die kleinste Zahl ganz vorne stehen.
(2) Tabelle: Kleinste Zahl an den Anfang
Jetzt ohne Hilfe: Tragen Sie nach jedem Vergleich ein, wie das Array aussieht. Mit »Prüfen« sehen Sie, welche Einträge stimmen – und bei jeder richtigen Zeile, welche beiden Zahlen verglichen und ob sie getauscht wurden.
Das ganze Array sortieren
Was ist ein Durchgang bei Selection Sort?
Ein Durchgang ist ein kompletter Durchlauf des Kleinste-Zahl-an-den-Anfang-Algorithmus durch den noch unsortierten Teil des Arrays: Das erste Element dieses Teils wird nacheinander mit allen Elementen dahinter verglichen und sofort getauscht, wenn eines kleiner ist. Am Ende des Durchgangs steht die kleinste noch unsortierte Zahl vorne an ihrem endgültigen Platz.
- Im 1. Durchgang wird mit array[0] verglichen, im 2. Durchgang mit array[1] und so weiter.
- Jeder Durchgang ist um einen Vergleich kürzer als der vorige – vorne wird der sortierte Bereich immer größer.
- Ein Array mit n Elementen braucht n − 1 Durchgänge, dann ist es sortiert.
(3) Schritt für Schritt: Selection Sort komplett
Jetzt alle Durchgänge. Oben sehen Sie, in welchem Durchgang Sie gerade sind. Der grau dargestellte Bereich vorne ist schon fertig sortiert.
(4) Münzen sortieren
Sortieren Sie die Münzen mit Selection Sort nach ihrem Wert – die kleinste Münze soll am Ende ganz links liegen. Verglichen werden immer die beiden grün umrandeten Münzen. Ist die hintere weniger wert als die vordere, ziehen Sie sie auf die vordere (auf dem Handy: mit dem Finger ziehen oder beide Münzen nacheinander antippen).
(5) Tabelle: Namensliste sortieren
Die Namensliste vom Arbeitsblatt – diesmal online. Sortieren Sie die Namen alphabetisch mit Selection Sort und tragen Sie nach jedem Vergleich den Zustand ein.
(6) Tabelle: Ergebnis nach jedem Durchgang
Wie in der Klassenarbeit: Tragen Sie das Ergebnis nach den einzelnen Durchgängen ein. Mit »Neue Werte« bekommen Sie ein neues Array.
Selection Sort verstehen
(7) Wie oft wird verglichen?
Wie viele Durchgänge, wie viele Vergleiche, wie viele Vertauschungen? Rechnen Sie, bevor Sie »Prüfen« drücken – danach sehen Sie die Lösung an einem ausführlichen Beispiel.
(8) Münzen nach dem Durchgang hinlegen
Oben sehen Sie, wie die Münzen am Anfang liegen. Spielen Sie den Durchgang im Kopf durch und ziehen Sie dann die Münzen vom Haufen auf die Array-Plätze, an denen sie danach liegen. (Auf dem Handy: Münze antippen, dann den Platz antippen.)
(9) Fehler finden
Hier wurde nach jedem Durchgang notiert, wie das Array aussieht – aber einmal ist etwas schiefgegangen.
(10) Bubble Sort oder Selection Sort?
Jetzt kennen Sie beide Algorithmen. Erkennen Sie an der Tabelle, welcher von beiden hier am Werk war?