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:

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.

#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>

#define DIM 100000

main()
{
        struct tms buffer;
        int feld[DIM];
        int feld_kopie[DIM];

        int i;
        for (i=0;i<DIM;i++)
                {
                feld[i] = feld_kopie[i] = rand();
                }
        times(&buffer);
        printf("Zeit vor dem Sortieren: %d\n",buffer.tms_utime);
        my_qsort_000000(feld, DIM );
        times(&buffer);
        printf("Zeit vor dem UNIX Sortieren: %d\n",buffer.tms_utime);
        my_qsort_000000(feld_kopie, DIM );
        times(&buffer);
        printf("Zeit nach dem UNIX Sortieren: %d\n",buffer.tms_utime);

        if (memcmp(feld,feld_kopie, DIM * sizeof(int) ) != 0)
                printf("Wir haben Probleme, die beiden Felder sind nach dem Sortieren verschieden\n");
}

my_comp(int *a, int *b)
{
        return *a - *b;
}

my_qsort_000000(int *feld, int feld_laenge)
{
        qsort(feld,feld_laenge, sizeof(int), my_comp);
}
 

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 xⁿ 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)