Praktikum Datenverarbeitung 4. Arbeitsblatt

WS 1997/98 - Fachhochschule Köln
Fachbereich Nachrichtentechnik
Dr. Matthias Groß

Praktikum Datenverarbeitung - 4. Arbeitsblatt

Abgabetermin für alle: Montag 26.01. 1998 im DV-Labor

Bei dieser Praktikumsaufgabe soll die Codierung von Struktogrammen in die Programmiersprache C und der kritische Vergleich von Algorithmen eingeübt werden.

Aufgabe 13:

Schreiben Sie zu den drei Sortieralgorithmen BubbleSort, InsertSort und HeapSort jeweils ein Unterprogramm, welches ein Feld von Integerzahlen sortieren kann. Die Datenübergabe des Feldes erfolgt in der Form

```
void SortAlg(int *data, int datasize);
```

wobei data ein Zeiger auf das zu sortierende Feld ist und datasize die Anzahl an Elementen in diesem Feld angibt.

Vergleichen Sie die drei von Ihnen programmierten Algorithmen, indem Sie von einem Testprogramm ( void main() ) für jeden Algorithmus folgende Tabelle bestimmen lassen:

Zeiten beim Sortieralgorithmus ....	100 Elemente	1.000 Elemente	10.000 Elemente
Best Input	Zeit 1	Zeit 4	Zeit 7
Average Input	Zeit 2	Zeit 5	Zeit 8
"Worst Input"	Zeit 3	Zeit 6	Zeit 9

Hierbei ist Best Input der Fall, in dem das Feld bereits sortiert ist, d.h. data[n]=n gilt, Worst Input der Fall, in dem die Daten maximal unsortiert sind, d.h. data[n]=datasize-n gilt, und Average Case der Fall, in dem die Daten zufällig verteilt sind.

(Anmerkung: Der Worst Case bezeichnet generell den Fall, in dem der Algorithmus die längeste Zeit zur Ausführung benötigt. Dies muß nicht unbedingt der Fall des Worst Input sein, sondern ist eine Eigenschaft des Sortieralgorithmus)

Verwenden Sie für die Initialisierung der zufälligen Daten die Funktion randomize(), um zu Beginn des Programmlaufs den Zufallszahlengenerator zu starten, und bestimmen Sie mit rand() die einzelnen Werte. Vergleichen Sie hierzu bitte auch die Online-Hilfe unter Borland C++.

Um die Zeiten zu stoppen, verwenden Sie die Funktion time_t time(0), die die aktuelle Anzahl der Sekunden seit dem 01.01.1970 angibt. Um Zeiten genauer als 1 Sek. zu stoppen, führen Sie die entsprechenden Sortieralgorithmen n-mal (mit n geeignet groß) hintereinander aus. Ein Beispiel, wie die oben angesprochenen Funktionen zu verwenden sind, wird auch noch in der Vorlesung gegeben.

Die erstellten Tabellen mit einer kurzen schriftlichen Interpretation gehören zur Programmabgabe dazu.