Die Aufgaben sollen in Zweiergruppen bearbeitet werden. Dreiergruppen
sind nicht zulässig
Jede Aufgabe soll auf einem Extrablatt bearbeitet werden. Bitte
auf jedem Blatt Name/Matrikelnummer notieren
URL: /axel/informatik2_ss01_blatt3.html
Alles über Quicksort
Aufgabe 5(3 + 3 + 2 Punkte)
Wir nehmen bei a) und b) an, dass es sich um verschiedene Einträge
handelt. Falls es für Ihre Überlegungen wichtig ist, spezifizieren
Sie welche Quicksort Variante gemeint ist
(z.B. Sedgewick) und auch welches Vergleichselement (erstes, letztes,
etc.) gewählt wird.
a) Man berechne die Wahrscheinlichkeit, daß beim Sortieren eines
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 eines
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.
Aufgabe 6 (10 Programmierpunkte - Abgabe per email bis 24.5.01 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.
#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. Als Vergleichsroutine
wurde die system implementierung von qsort verwendet. 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 7( 2 + 3 + 3 Punkte)
In der Vorlesung wurden unterschiedliche Quicksortvarianten vorgestellt.
Hier sortiert absteigend nach der Qualität
a) Sedgewick
b) Rekursiv mit Kopieren, das kleinste Teilfeld wird zuerst weitersortiert
c) Rekursiv mit Kopieren
Wir betrachten den worst case. Bis zu welcher Grösse können
int-Felder sicher sortiert werden bei folgenden Rahmenbedingungen:
- wir haben 128MB Speicher zur Verfügung
- wir betrachten nur den Speicher benötigt für das zu sortierende
Feld, Variablen und Programmcode wird vernachlässigt
- eine einzelne int Variable benötigt 4 Byte
Aufgabe 8 (4+4 Programmierpunkte - Abgabe per email bis 31.5.01
10.00 Uhr)
Verifizieren Sie die Überlegungen aus Aufgabe 7 indem Sie zwei
weitere Routinen: