URL:         /axel/informatik2_ss00_blatt3.html

Die Programmieraufgaben sind alleine zu bearbeiten, die anderen Aufgaben können in Zweiergruppen bearbeitet werden.

Aufgabe 5 (10 Programmierpunkte - Abgabe per email bis 25.5.00 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 6 (3 + 3 + 2 Punkte)
a) Man berechne die Wahrscheinlichkeit, daß beim Sortieren eine Feldes der Länge n mit Quicksort die maximale Anzahl von Vergleichen nötig ist. (worst case)
b) Man berechne die Wahrscheinlichkeit, daß beim Sortieren eine Feldes der Länge n mit Quicksort die minimale Anzahl von Vergleichen nötig ist.
c) Gebe für jedes n eine Folge der Zahlen 1....n an, bei der die minimale Anzahl von Vergleichen benötigt wird.