Übungen zum Thema Sortieren und zum Debugging

Aufgabe 1: Elemente eines Felds umkehren

Gegeben sei folgendes Feld:

int data[] = {0, 1, 2, 3, 4};

Kehren Sie die Reihenfolge der Zahlen im Feld data um

Tun Sie dies im ersten Schritt mit einzelnen Zuweisungen
Entwickeln Sie diese Lösung im zweiten Schritt zu einer verbesserten Lösung weiter, die eine Schleife benutzt
Geben Sie das umgekehrte Feld jeweils mit einer Schleife aus

Benutzen Sie für das Umkehren kein zweites Feld, sondern vertauschen Sie die Feldelemente im Feld data selbst, durch Einsatz einer Hilfsvariable temp.

Programmausgabe:

Aufgabe 2: Elemente umgekehrt in ein zweites Feld schreiben

Gegeben sei folgendes Feld:

int data[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};

Schreiben Sie Programmcode, der die Reihenfolge der Elemente in data umkehrt. Verwenden Sie hierfür zwei Felder und keine Hilfsvariable, wie bei der Lösung der Aufgabe oben.

Das erste Feld data wird nicht geändert. Das zweite Feld result erhält die Elemente von data in umgekehrter Reihenfolge eingeschrieben.

Geben Sie am Ende die Elemente des Felds result mit Hilfe einer Schleife aus.

Programmausgabe:

[14] [13] [12] [11] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]

Aufgabe 3: Maximumsuche

In unserer Entwicklungsumgebung existiert ein wichtiges Werkzeug, welches die Fehlersuche in Programmen immens vereinfachen kann: Der Debugger.

Der Debugger gehört zu den grundlegenden Werkzeugen einer integrierten Entwicklungsumgebung.

In dieser Übung werden wir die Funktion des Debuggers in Processing näher kennenlernen.

Implementieren Sie zunächst unter Processing den in der Vorlesung behandelten Algorithmus zur Maximumsuche mit Feld (Seite 266), z. B. als neue Sketch, und führen Sie ihn danach aus.

Als Programmausgabe sollte folgendes erscheinen:

Diesen Algorithmus werden wir nun mit Hilfe des Debuggers untersuchen.

Debugging

Der Debugger gestattet es, ein Programm schrittweise auszuführen, um seine Funktion zu analysieren und dabei Variablenwerte einzusehen und diese während der Laufzeit des Programms ggf. auch zu ändern. Auf diese Weise lassen sich schwer zu findende Programmfehler leichter lokalisieren, als mit einfachen Textausgaben auf die Konsole.

Hierfür benötigt der Debugger Informationen darüber, wie die in der Quelldatei definierten Symbole, d. h. hier zur Zeit in erster Linie die Variablen, in Beziehung stehen zum erzeugten Maschinencode. Diese Informationen werden bei der Übersetzung des Quellcodes von Processing automatisch erzeugt.

Aktivieren Sie den Debugger in Processing durch einen Klick auf folgendes Icon:

Der Debugger ist nun aktiv geschaltet (blaues Icon) und das Überwachungsfenster für die Variablen öffnet sich zusätzlich. Sollte diese Fenster verloren gehen, einfach den Debugger deaktivieren und erneut aktivieren.

Links sind neue Buttons dazugekommen. Neben den bekannten "Starten" und "Stoppen", sehen wir jetzt auch noch "Schritt" und "Weiter". Anstatt "Starten", heisst der Button jetzt "Debug".

Klicken Sie zuerst auf den Button "Debug" ... Das Programm startet nun - wie gewünscht - im Debugger und produziert die folgende Ausgabe:

Programmausführungen unter dem Debugger unterscheiden sich also zunächst nicht von normalen Programmausführungen. Um den Programmcode untersuchen zu können, muss zuvor mindestens ein Unterbrechungs- bzw. Haltepunkt (engl.: breakpoint) definiert werden.

Definieren Sie nun einen Haltepunkt in der Befehlszeile
```
int max = arr[0];
```
indem Sie auf die Zeilennummer klicken.

Es erscheint eine kleine blaue Raute, die für den eingefügten Haltepunkt steht. Durch einen weiteren Klick auf die blaue Raute kann man den Haltepunkt wieder entfernen. Lassen Sie diesen aber stehen und starten Sie das Programm im Debugger. Nun hält der Programmlauf am angegebenen Haltepunkt an, was durch einen kleinen Pfeil im Haltepunkt visualisiert wird. Zusätzlich ist die Programmzeile blau markiert, an der angehalten wurde.

Sobald das Programm am Haltepunkt wartet, sehen Sie im Überwachungsfenster für die Variablen, die Werte des zugehörenden Arrays. Mit dem Debugger lassen sich also Variablenwerte kontrollieren.

Gehen Sie jetzt im Programm durch Drücken des Einzelschrittbuttons ("Schritt") eine Befehlszeile weiter voran. Im Variablenfenster wird nun automatisch der neue Wert der Variable max angezeigt und nach einem weiteren Drücken die neu deklarierte Variable i hinzugefügt.

Drücken Sie einige Male den Einzelschrittbutton. Bei jedem Drücken wird genau ein Programmbefehl ausgeführt. Achten Sie dabei darauf, wie sich im Variablenfenster die Werte der Variablen i und max automatisch ändern. Auf diese Weise lässt sich kontrollieren, ob der Programmablauf und die Werte der Variablen den Erwartungen entsprechen. Durch fortgesetztes Drücken des Einzelschrittbuttons lässt sich bei Bedarf das Programm vollständig schrittweise abarbeiten.

Sind im Programmcode mehrere Breakpoints platziert, so kann der Code zwischen diesen Breakpoints durch Drücken des Buttons "Weiter" in einem Zug durchlaufen werden. Beginnend bei einem Breakpoint, läuft das Programm bis zum nächsten Breakpoint oder bis zum Ende, wenn kein weiterer Breakpoint bzw. Haltepunkt mehr existiert. Probieren Sie dies aus, indem Sie in Ihrem Programmcode zwei Breakpoints in einigem Abstand voneinander platzieren und die Befehle zwischen ihnen mit "Weiter" durchlaufen.

Nach dieser kurzen Einführung sind Sie jetzt mit den wichtigsten Funktionen des Debuggers vertraut.

Aufgabe 4: Maxsort und Minsort

Implementieren Sie den in der Vorlesung erläuterten Maxsort-Sortieralgorithmus.

Ändern Sie den Maxsort-Sortieralgorithmus zu einem Minsort ab, d. h. die Zahlen sollen jetzt aufsteigend sortiert werden.

Untersuchen Sie auch diesen Algorithmus mit dem Debugger, um dessen Ablauf schrittweise zu studieren. Der Debugger ist auch ein hervorragendes Instrument, um unbekannte Algorithmen zu analysieren und zu verstehen.

Aufgabe 5: Spielkarten mischen und sortieren

Ein Satz Spielkarten bestehe aus 32 Karten, mit jeweils 8 Herz-, Karo-, Kreuz- und Pik-Karten.

Schreiben Sie ein Programm, welches ein char-Feld von 32 Elementen mit 32 zufällig ausgewürfelten Karten belegt, wobei von jeder Farbe genau 8 Karten im Feld verteilt sind. Die Farben seien z. B. wie folgt codiert:
Herz: 'H'
Karo: 'K'
Kreuz: 'X'
Pik: 'P'

Geben Sie das gemischte Kartenspiel auf die Konsole aus.

Beispielprogrammausgabe:
Erweitern Sie Ihr Programm um eine Variante des Max- bzw. Minsort-Algorithmus, die das gemischte Kartenspiel so sortiert, dass am Ende von links nach rechts zunächst die Herz-Karten im Feld liegen, dann die Karo-Karten, danach die Kreuz-Karten und schließlich die Pik-Karten. Das Sortieren geschieht auf dem ursprünglichen Feld, ohne Hilfsfelder zu diesem Zweck zu benutzen. Geben Sie zur Kontrolle das sortierte Feld aus.

Programmausgabe:
Erweitern Sie Ihr Programm dahingehend, dass die Reihenfolge, in der die Karten zu sortieren sind, eingegeben werden kann:

Beispielprogrammausgabe 1:

Kreuz zuerst, dann Pik, dann Herz und zum Schluss Karo.

Beispielprogrammausgabe 2:

Aufgabe 6: Zeichenhäufigkeit

Schreiben Sie ein Programm, welches in einer Schleife über die Konsole nach einer Reihe von max. 50 Schriftzeichen fragt und diese in einem Feld vom Typ char abspeichert. Die Eingabe wird durch das Zeichen 0 beendet oder wenn mehr als 50 Zeichen eingegeben werden. Groß- und Kleinschreibung wird vernachlässigt. Das Feld wird danach absteigend, entsprechend der Codenummer der Zeichen in der Zeichentabelle sortiert (siehe der Beispielablauf unten), sodass das Zeichen mit der größten Codenummer im ersten Feldelement steht.

Nachfolgend wird die Häufigkeit, mit der die Zeichen im Feld vorkommen, gezählt und zusammen mit der Codenummer des Zeichens auf die Konsole ausgegeben.

Zeichen können Sie mit dem Befehl getChar der IOLib einlesen:

char ch = IOLib.getChar("Schriftzeichen eingeben (0: stop): ");

Beispielablauf:

Die Codenummer des Zeichens steht jeweils in eckigen Klammern. Die hier abgebildeten Codenummern entsprechen der von Windows im europäischen Raum auf der Konsole eingesetzten Codepage 850.