Im Spiel: wer steht vorn?
Optional. Diese Seite ist ein Zusatzangebot am Ende des Kapitels. Sie führt nichts Neues ein, und weder der Rückblick noch die späteren Kapitel setzen sie voraus.
Sortieren wirkt wie eine Sache für Datenbanken und Listen. Diese Seite zeigt eine Stelle, an der sechzigmal pro Sekunde sortiert werden muss – und an der ausgerechnet das langsamste Verfahren des Kapitels das richtige ist.
Scratch for Java in fünf Minuten
Diese Seite macht einen Entwurf mit der Grafikbibliothek Scratch for Java sichtbar. Du musst sie nicht kennen – hier steht alles, was du dafür brauchst. Geladen wird sie über libraries="scratch"; import-Zeilen gibt es nicht.
| Begriff | Was er bedeutet |
|---|---|
Stage |
die Bühne, 480 × 360 Pixel. Der Punkt (0, 0) liegt in der Mitte, die y-Achse zeigt nach oben. Man schreibt eine eigene Klasse, die von Stage erbt. |
Sprite |
eine Figur auf der Bühne. Auch dafür schreibt man eigene Klassen, die von Sprite erben. |
addCostume("coin_gold") |
gibt einer Figur ihr Bild. Die Bibliothek bringt über 1700 fertige Kostüme mit. |
this.add(objekt) |
fügt eine Figur oder einen Text der Bühne hinzu. Was nicht hinzugefügt wurde, sieht man nicht. |
run() |
wird für jedes Objekt etwa 60-mal pro Sekunde aufgerufen. Alles Fortlaufende steht hier drin. |
getTouchingSprite(Muenze.class) |
liefert das berührte Objekt oder null, wenn gerade keins berührt wird. Das null muss man immer abfragen. |
Dazu isKeyPressed(KeyCode.RIGHT) für die Tastatur, changeX(4) zum Bewegen, remove() zum Entfernen und new Text(text, x, y, breite) mit showText(...) für die Anzeige.
Zum Nachlesen: Die erste Grafik erklärt Bühne und Koordinatensystem, Eigene Sprites die eigenen Figurenklassen mit run(). Alle Methoden auf einen Blick: Referenz.
Woran es hakt
Die Bühne zeichnet ihre Figuren in der Reihenfolge, in der sie hinzugefügt wurden. Für ein Spiel mit Tiefe ist das die falsche Reihenfolge: Was weiter unten steht, ist näher am Betrachter und muss vor allem anderen gezeichnet werden.
Solange nichts sich bewegt, kann man die Figuren einmal in der richtigen Reihenfolge hinzufügen. Sobald sie sich bewegen, ändert sich die richtige Reihenfolge dauernd – und zwar in jedem Bild.
Die Zeichenreihenfolge ergibt sich aus der y-Koordinate: Wer den kleineren y-Wert hat, steht weiter vorn und wird zuletzt gezeichnet.
Aus einer Menge von Figuren eine Reihenfolge zu machen, ist nichts anderes als Sortieren – nur mit der y-Koordinate als Schlüssel.
Welches Verfahren passt?
Die Reflexantwort lautet Quicksort: O(n·log n) im Mittel, besser geht es nicht. Sie ist hier falsch, und der Grund steht in der Tabelle aus dem Rückblick:
| Verfahren | mittlerer Fall | erkennt schon sortierte Daten |
|---|---|---|
| Sortieren durch Einfügen | O(n²) | ja – dann nur O(n) |
| Quicksort | O(n·log n) | nein |
Zwischen zwei Bildern vergeht etwa eine Sechzigstelsekunde. In dieser Zeit bewegt sich keine Figur weit genug, um an einer anderen vorbeizuziehen – meistens jedenfalls.
Das heißt: Das Feld ist beim nächsten Aufruf schon sortiert, bis auf ein paar Nachbarn. Genau für diesen Fall ist Sortieren durch Einfügen gebaut. Es geht einmal durch und stellt fest, dass nichts zu tun ist.
Quicksort dagegen teilt und teilt, egal wie die Daten aussehen. Es kann von der Vorarbeit des letzten Bildes nicht profitieren.
Die O-Notation beschreibt das Verhalten bei wachsender Eingabe im allgemeinen Fall. Sie sagt nichts darüber, welches Verfahren bei dieser Eingabegröße und diesem Vorwissen schneller ist. Hier ist n klein und die Eingabe fast sortiert – zwei Bedingungen, unter denen sich die Rangfolge umdreht.
Im Spiel
Unten schwimmen acht Figuren auf und ab. Das Feld wird in jedem Bild neu sortiert, und die Anzeige zählt, wie viele Verschiebungen das Sortieren durch Einfügen dafür gebraucht hat.
Sieh der Zahl beim Laufen zu: Sie ist fast immer 0 und springt nur dann kurz hoch, wenn zwei Figuren sich tatsächlich überholen.
Aufgabe 1: messen statt glauben
a) Sage voraus, wie viele Verschiebungen im ersten Bild nötig sind, und vergleiche mit der Anzeige. Warum ist gerade dieser erste Wert so viel größer als alle folgenden?
b) Erhöhe das Tempo der Figuren auf 8. Was macht die Zahl – und warum?
c) Setze die Zahl der Figuren auf 40. Bleibt die Zahl der Verschiebungen klein? Wie viele Vergleiche macht das Verfahren dabei mindestens pro Bild, auch wenn nichts zu tun ist?
d) Ersetze das Sortieren durch Einfügen durch Quicksort. Zähle die Vergleiche statt der Verschiebungen. Was ändert sich an der Zahl, wenn das Feld schon sortiert ist?
Die Bestenliste
Am Ende einer Runde will man wissen, auf welchem Platz man steht. Hier sieht es anders aus: Die Punktzahlen kommen unsortiert an, es sind viele, und sortiert wird einmal. Das ist genau der Fall, für den Quicksort gebaut ist.
Aufgabe 2: Bestenliste
a) Sortiere ein Feld int[] punkte mit Quicksort absteigend und gib die besten fünf aus.
b) Schreibe platzVon(int[] pPunkte, int pWert): Auf welchem Platz steht diese Punktzahl in der sortierten Bestenliste? Nutze die binäre Suche – und achte darauf, dass absteigend sortiert ist.
c) Warum darf man die binäre Suche hier überhaupt einsetzen, bei den Figuren aber nicht?
d) Eine neue Punktzahl kommt dazu. Vergleiche zwei Vorgehen: alles neu sortieren, oder die Zahl mit binärer Suche einordnen und einfügen. Welches ist bei 10 Einträgen besser, welches bei 10 000?
Und ohne Spiel?
| Im Spiel | Dieselbe Überlegung woanders |
|---|---|
| in jedem Bild neu sortieren, Daten fast sortiert | Messwerte, die laufend nachkommen; Tabellen, die sich kaum ändern |
| einmal sortieren, viele Daten | Bestenliste, Suchergebnisse, Notenliste |
| binäre Suche in der Bestenliste | Nachschlagen in einem sortierten Verzeichnis |
| Quicksort im schlechtesten Fall | vorsortierte Eingabe bei fester Trennelement-Wahl |
Die Einsicht des Kapitels lautet nicht „Quicksort ist das beste Verfahren". Sie lautet: Welches Verfahren passt, entscheidet nicht die O-Notation allein, sondern das, was man über die Daten weiß.