Prof. Dr. R. Laue                                                                                                                                  SS98
                                Informatik II
                                Übungsblatt 2
                                Abgabe: 22.05.98 bis 10.00 Uhr im Raum 736 NW2 zweiter Stock
 
URL:         /axel/informatik2_ss98_blatt2.html
Dieses  Übungsblatt ist in Zweiergruppen zu  bearbeiten.

Aufgabe 3 (10 Programmierpunkte - Abgabe per email bis 28.5.98 10.00 Uhr)
Schreiben Sie eine C Funktion mit dem Namen my_qsort_matrikelnummer(), welche ein int-feld  mit der Quicksortvariante von Sedgewick sortiert.
Die Deklaration der Funktion ist:

int my_qsort_matrikelnummer(int *feld, int feld_laenge)

Der zweite Parameter ist die Anzahl der Einträge im zu sortierenden Feld. Beim Namen der Routine ist matrikelnummer durch eine Ihrer Matrikelnummern zu ersetzen. Folgendes C Programm, bzw deren main-routine, soll nach Anpassung der Matrikelnummer als Testfunktion verwendet werden können.

 

Der erste Aufruf von ...000000 soll ersetzt werden durch den Aufruf Ihrer Routine. Im  Beispiel wurde die Systemfunktion times() verwendet, mit ihr kann die bisherige Rechenzeit festgestellt werden. Am Ende wird mit der Systemfunktion memcmp() getestet ob die sortierten Felder identisch sind. Die Verwendung von times() geht nur auf UNIX Rechnern. Will man unter Windows arbeiten, so sollte man sich die Funktion clock() anschauen.

Aufgabe 4 (5 Punkte)
Beweisen Sie, daß die Quicksortvariante von Sedgewick auch Felder mit identischen Einträgen korrekt sortiert.

Aufgabe 5 (6 Punkte)
Man entwerfe einen divide and conquer Algorithmus zur Berechnung der Potenz xn einer reellen Zahl x und einer natürlichen Zahl n.
 
Aufgabe 6 (4 + 3 Punkte)
Führen Sie den Heapsort mit dem Feld der Länge 14 durch, welches sie durch die Verknüpfung Ihrer beiden Matrikelnummern bekommen. Stellen Sie dabei die Zahlenfolge als Baum dar. (4 Punkte)
Ein Sortieralgorithmus ist stabil, wenn sich die Reihenfolge von Datensätzen mit gleichen Schlüssel sich während des Sortieralgorithmus nicht ändert.
Ist Heapsort stabil? Beweis! (3 Punkte)