Aufgabenblatt 11: Rekursion & Sortieren

Aufgabe 11.1: Bubblesort

Implementieren Sie den in der Vorlesung besprochenen Bubblesort-Algorithmus in einer eigenen Klasse mit einer Methode public void sort(int[] a)!

Testen Sie Ihren Algorithmus an einer Liste von 100 zufälligen Zahlen zwischen 0 und 9999.

Aufgabe 11.2: Gnomesort

Ein weiterer einfacher, mit Bubblesort verwandter, Sortieralgorithmus ist Gnomesort (engl. garden gnome = Gartenzwerg)¹:

Man stelle sich einen Gartenzwerg vor, welcher vor n Blumentöpfen steht, die unterschiedliche Größen haben dürfen. Die Blumentöpfe sind in einer von links nach rechts verlaufenden Reihe aufgestellt. Ganz links steht der Gartenzwerg und möchte die Blumentöpfe von links nach rechts der Größe nach aufsteigend sortieren.

Dazu vergleicht er die beiden Blumentöpfe, vor denen er grade steht. Stellt er fest, dass sie in der richtigen Reihenfolge sind, so macht er einen Schritt nach rechts. Stellt er hingegen fest, dass die Reihenfolge nicht stimmt, so vertauscht er die beiden Blumentöpfe und macht einen Schritt nach links. Falls er nicht weiter nach links gehen kann (wenn beispielsweise der erste Vergleich zum Ergebnis führte, dass sich der erste und zweite Blumentopf in der falschen Reihenfolge befanden), macht er einen Schritt nach rechts. Dies wiederholt er ständig. Fertig ist er, wenn er am ganz rechts stehenden Blumentopf ankommt. Da sich rechts daneben kein weiterer Blumentopf mehr befindet, kann kein Vergleich mehr stattfinden.

Implementieren Sie diesen Algorithmus in Java!

Aufgabe 11.3: Sortierrennen

Lassen Sie Ihre Implementierungen Bubblesort und Gnomesort) gegeneinander antreten, optional auch gegen Insertionsort und Selectionsort aus der Vorlesung!

Dazu sollen die Laufzeiten der Algorithmen mit drei unterschiedlichen Arten von Eingangsdaten gemessen werden: Zufällige Daten, aufsteigend vorsortiert, absteigend vorsortiert.

Eine sinnvolle Datenbasis für die Messung sind 20 Durchläufe mit einem Array mit 20000 Einträgen.

Ihr Programm soll eine Tabelle mit Ergebnissen auf der Konsole ausgeben:

|               |zufällig   |aufsteigend|absteigend |
|---------------|-----------|-----------|-----------|
|Bubblesort     |xx ms      |xx ms      |xx ms      |
|Gnomesort      |xx ms      |xx ms      |xx ms      |
|Insertionsort  |xx ms      |xx ms      |xx ms      |
|Selectionsort  |xx ms      |xx ms      |xx ms      |

Hinweis:

Zur Zeitmessung können Sie die Methode System.nanoTime() nutzen, die die Systemzeit in Nanosekunden zurückgibt:

long start = System.nanoTime();
// Codebereich, dessen Laufzeit gemessen wird
long dauer_ns = System.nanoTime() - start;
long dauer_ms = dauer_ns / 1000 / 1000;