Blatt 2

Übungen zu Systemnahe Software

Wintersemester 95/96

Sektion Angewandte Informationsverarbeitung

Abgabe: Donnerstag, 09.11.95

Aufgabe 1: 7 Punkte

Sie sitzen spät abends an der Bar und grübeln über ihrem gerade wieder leer gewordenen Glas. Verzweifelt versuchen sie, die Trümmer ihrer Informatikkenntnisse aus den ersten beiden Semestern zu sortieren. "Quicksort, Bubblesort, Urlaubsort ...", sinnieren sie. "Das Leben ist ein einziges Auf und Ab", sagt der Barmann tröstend, der gerade einen Martini für ihren - in letzter Zeit etwas seltsam gewordenen - Freund 007 schüttelt.

Da kommt ihnen eine Idee. Sie werfen dem Barmann einen abgegriffenen 30 DM-Schein hin, warten nicht auf das Wechselgeld, torkeln zum heimischen Schreibtisch - und: erfinden den Shakersort.

Da sie seit der Trennung von ihrer Freundin einen leichten Zug zum Selbstquälen haben, entschließen sie sich, den Algorithmus in einem C-Programm zu implementieren, das (maximal 3000) Zahlen von der Standardeingabe liest und anschließend shakermäßig sortiert und ausgibt. Um das Eingabeende der Zahlenreihe zu erkennen, schauen sie sich zum ersten Mal im Leben eine Manualseite an: die von scanf(). Der schnöden Ordnung zuliebe beschließen sie großzügig die Verwendung von Funktionen, die ihr Programm übersichtlich machen. An der Prozedur void shakersort(int tosort[], int num), die ihnen num eingelesene Zahlen im Array tosort sortiert, kommen selbst sie nicht vorbei ...

Hier nun der von ihnen erfundene Algorithmus für den Shakersort:

Die Zahlen im Array a[] ablegen - vom Anfang bis zum Ende des Arrays laufen - immer die aktuelle Zahl a[i] mit deren Nachfolger a[i+1] vergleichen - ist a[i+1] kleiner, werden die beiden getauscht - am Ende des Arrays rückwärts laufen - a[i] mit a[i-1] vergleichen - ist a[i] kleiner, werden beide getauscht - dieses Auf und Ab solange durchführen, bis bei einem Durchgang nichts mehr getauscht wurde - fertig sortiert!

Aufgabe 2: 3 Punkte

Sie beschließen ihre Erfindung gegen bestehenden Sortieralgorithmen antreten zu lassen. Schreiben sie deshalb mit Hilfe der C-Büchereifunktion qsort() ein Programm, das ihre Zahlenreihe mit Hilfe des Quicksort sortiert, und vergleichen sie anschließend die Laufzeiten der beiden Programme bei identischen Zahlenreihen. Das klappt mit dem time-Kommando (man time) unter UNIX. Was fällt ihnen auf? Variieren sie die Länge ihrer Zahlenreihen!

Hinweis: (keine Panik!) der Quicksort ist fix und fertig in der Bücherei implementiert. Sie müssen ihn nur richtig aufrufen. Hier eine benötigte Funktion und der qsort-Aufruf (siehe auch man qsort):

int compare(a, b) /* Vergleichsfunktion für zwei Integer, gegeben durch zwei Zeiger */

int *a, *b;

{ if (*a > *b) return 1;

if (*a < *b) return -1;

return 0; /* bei *a == *b */

}

Der Aufruf in ihrem Programm sollte dann lauten:

qsort(tosort, num, sizeof(int), compare) mit int tosort[]; int num; int (*compare)();

(compare ist also ein Zeiger auf die Vergleichsfunktion).