Übungen und Miniprojekte

Bubble-Sort

Ein ganz häufige Aufgabe in der Informatik ist das Sortieren von Dingen. Du verwendest dies zum Beispiel beim auf- oder absteigenden Sortieren bei einem Tabellenkalkulationsprogramm.

Wir werden im folgenden Beispiel eine Liste von Daten mit Snap! sortieren. Es gibt ganz verschiedene Vorgehensweisen zum Sortieren von Informationen.
Man könnte z. B. einfach nacheinander Elemente von der ungeordneten Liste nehmen und in eine neue Liste sortiert einfügen.
Wir verwenden ein Verfahren, das besonders leicht zu verstehen und zu programmieren ist, da so genannte Bubble-Sort-Verfahren. Dazu vergleicht man einfach das 1. Element der Liste mit dem 2. Element und vertauscht die beiden, wenn das 1. Element größer als das zweite ist bzw. im Alphabet hinter dem 2. Elemet steht. Nun vergleicht man das 2. mit dem 3. Element, das 3. mit dem 4. Elemen usw. bis man die letzen beiden Elemente verglichen und ggf. vertauscht hat. Die folgende Animation zeigt dies:

Dieses Vorgehen bewirkt, dass größere Elemente weiter nach hinten (oder je nach Sichtweite nach oben bewegt werden, wie sich Luftblasen in einer Sprudelflasche nach oben bewegen. Daher der Name Bubble-Sort.

Nach dem Durchlaufen der Liste befindet sich also das größte Element am Ende der Liste und damit an der richtigen Stelle.

Den gleichen Durchlauf wiederholt man nun und sorgt dafür, dass sich damit das zweitgrößte Element an der vorletzten Stelle befindet.
Insgesamt benötigt man also maximal so viele Durchläufe wie sich Elemente in der Liste befinden (genauer: einen Durchlauf weniger als die Anzahl der Elemente in der Liste).

Das in der Animation gezeigte Vertauschen von Elementen müssen wir noch etwas genauer betrachten. Ein direkter Tausch von zwei Speicherplätzen ist nämlich nicht möglich. Wir benötigen noch einen Zwischenspeicher. Der Tausch erfolgt dann in drei Schritten

1. Kopieren des ersten Elements in den Zwischenspeicher.
2. Kopieren des zweiten Elements in das erste Element.
3. Kopieren des Zwischenspeichers in das zweite Element.

Die folgende Animation zeigt das Vorgehen:

Um eine Liste von Zahlen zu veranschaulichen verwenden wir einen vorgegebenen Block . Damit werden die Zahlen der Liste nebeneinander als Säulen entsprechender Höhe dargestellt.
Beispiel:

Nun können wir den Bubble-Sort-Algorithmus implementieren. Insgesamt benötigen wir also so viele äußere Wiederholungen wie die Anzahl der Elemente der Liste (Wiederholung mit fester Anzahl). Bei jeder inneren Wiederholung (hier eignet sich eine for-Wiederholung mit der Zählvariablen ) zählen wir von 2 bis zur Anzahl der Listenelemente . Sollte das jeweils links stehende Listenelement (Index ) größer als das momentane Listenelement sein, ist eine Vertauschung der beiden notwendig. Nach jedem Hochzählen in der inneren Wiederholung zeichnen wir die Liste neu, um die Änderung sichtbar zu machen.

Sortiertes Einfügen

Häufig möchte man, dass die Elemente in einer Liste aufsteigend sortiert sind, z. B. nach der Größe bei Zahlen oder alphabetisch bei Texten. Sortierte Listen sind vor allem zur Suche von Elementen hilfreich.

Die Lösung dieser Aufgabe ist ohne Unterstützung eher schwer. Deshalb drei gestufte Hilfestellungen dazu:

Simon

Shritwod, CC0, via Wikimedia Commons

Simon (auch Sensori genannt) ist ein Gedächtnisspiel, bei dem es darum geht, sich eine Folge von Farben, die akustisch mit Tönen hinterlegt sind, zu merken.
Die Spielerin/ der Spieler muss eine vorgegebene Farbfolge (aufleuchtende farbige Tasten) durch Drücken der Farbtasten nachverfolgen. Nach jedem Durchgang wird an die bisherige Folge eine neue zufällige Farbe angehängt.
Das folgende Video zeigt einen möglichen Spielverlauf.

Die Programmierung des Spiels ist auf ganz verschieden Arten möglich. Im Folgenden wird eine Möglichkeit vorgestellt, bei der eine ganze Reihe von Programmierkonzepten zum Einsatz kommt und die damit eher anspruchsvoll ist.

Zur Umsetzung des Spiels sollte sich man zunächst überlegen, welche Sprites dafür notwendig sind.
Offensichtlich benötigen wir für jede der vier Farben ein Sprite, so dass wir auf das Anklicken reagieren können. Außerdem benötigen wir noch ein Skript, das den ganzen Spielablauf steuert. Die Spielsteuerung könnte als Skript für den Hintergrund hinterlegt werden. Alternativ kann man auch ein eigenes Sprite für die Spielsteuerung anlegen.

Das Spiel kann sich in drei verschiedenen Zuständen befinden:

1. Der Computer spielt eine Folge von Farben vor.
2. Die Spielerin/ der Spieler versucht die Farbfolge durch Anklicken der farbigen Grafiken wiederzugeben.
3. Das Spiel wurde durch Anklicken einer falsche Farbe beendet (Game over).

Den Zustand des Spiels oder allgemein eines Systems speichert man üblicherweise als Zahl oder Text in einer Variable, z. B. in . Mögliche Werte der Variablen könnte vorspielen, nachspielen und gamover sein. Alternativ kann man die Spielzustände auch mit den Zahlen 1, 2 und 3 darstellen.

Da das Spiel interaktiv ist, d. h. auf Benutzereingaben reagiert, müssen die Sprites untereinander kommunizieren, also Informationen austauschen. In Snap! geht das auf zweierlei Arten:
Entweder man ruft einen Block eines anderen Sprites auf, z. B. mit .
Bei der zweiten Möglichkeit sendet man eine Nachricht an ein oder an alle Sprites. Der gewünschte Empfänger (Sprite) kann dann darauf reagieren:
sendendes Sprite:

empfangendes Sprite:

alternativ:

Zunächst erstellen wir vier Sprites, die jeweils zwei rechteckige Quadrate als Kostüme haben: aktiv (heller Farbton) und passiv (dunklerer Farbton). Wir bezeichnen die vier Sprites mit objekt1 bis objekt4.

Die Verschiebbarkeit der Sprites sollte deaktiviert werden.

Die Sprites haben jeweils nur ein ganz einfaches Skript. Beim Drücken senden sie eine Nachricht mit einer Nummer 1 bis 4. Für das Objekt2 ergeben sich sich folgende Blöcke.

Zum Abspielen der Töne und zum Aufleuchten lassen der Tasten erstellen wir einen eigenen Block , da dies mehrmals benötigt wird. Dafür eignet sich am besten eine Prozedur mit einem Parameter, der eine Zahl für die entsprechende Farbtaste erwartet. Die Prozedur sorgt dafür, dass Abhängig vom Parameter ein bestimmter Ton gespielt wird und während dieser Zeit das Kostüm gewechselt wird. Da die Tasten zu Beginn das dunkle Kostüm verwenden und jeweils zwei Kostüme existieren, geht das am einfachsten mit dem Block .

Für die eigentliche Spielsteuerung verwenden wir ein eigenes Sprite sowie eine Liste zum Abspeichern der Tastenfolge.

Für das Vorspielen einer Folge mit einem weiteren neuen Ton erzeugen wir einen eigenen Block:

Während des Spiels gibt es drei Zustände:

• Die Folge von Tasten wird gerade vorgespielt.
• Die Folge muss vom Spieler wiederholt werden.
• Das Spiel ist zu Ende, weil der Spieler eine falsche Taste gedrückt hat.

Den jeweiligen aktuellen Spielzustand speichern wir in einer Variable . Die mögliche Werte sind: vorspielen, nachspielen und gameover

Beim Nachspielen müssen wir kontrollieren, ob die Tasten in der richtigen Reihenfolge gedrückt werden. Dazu speichern wir Listenindex des nächsten Tones in einer Variable .

Beim Starten des Spieles wird kurz gewartet, die Sprechblase geleert, die Liste auf eine leere Liste gesetzt, eine neue Tonfolge vorgespielt, der Spielstatus auf nachspielen gesetzt und die Variable auf 1 gesetzt:

Dann muss der Spieler die passenden Tasten drücken. Dabei wird ja eine Nachricht mit der Nummer der entsprechenden Taste gesendet. Auf diese Nachricht müssen wir nun reagieren, aber nur beim Spielzustand nachspielen.
Falls es die richtige Taste für das aktuelle Listenelement war, erhöhen wir um 1, andernfalls ertönt ein tiefes Brummen für das Spielende.
Außerdem überprüfen wir anschließend, ob das Ende der Tonfolge erreicht ist. In diesem Fall ändern wir den Spielstatus auf vorspielen, warten kurz und rufen wieder den Block auf:

Damit ist das Spiel fertig.

Das Spiel hat noch einen Schönheitsfehler: Wenn während des Vorspielens eine Taste gedrückt wird, kommt es zu einem Fehler und das Spiel stoppt. Vielleicht hast du eine Idee, wie man das verhindern kann.
Tipp: Eine Taste darf eigentlich nur im richtigen Spielzustand zu drücken sein.