Universität Mannheim
Lehrstuhl für Praktische Informatik IV
Prof. Dr. W. Effelsberg
R. Lienhart 416
S. Pfeiffer 417

Bitte unbedingt beachten:

Die Programme müssen in ANSI-C geschrieben werden.
Sie müssen im Pool mit dem GNU C-Compiler gcc -Wall -ansi -pedantic fehlerfrei übersetzbar und lauffähig sein.
Wenn mehrere Dateien mit der abox abgegeben werden sollen, müssen sie vorher mit dem Befehl tar zu einer Datei zusammengebunden werden.

Übungsblatt 4

Abgabe: 30.11.95 um 12:00 Uhr

Aufgabe 1 [30 Punkte]

Implementieren Sie folgende Sortierverfahren als Funktionen. Es sollen Integer-Zahlen sortiert werden.
- Selection Sort
- Insertion Sort
- Bubble Sort
- Shell Sort
- Quicksort
- Heap Sort
Schreiben Sie zu jeder Sortierfunktion ein Programm, das die zu sortierenden Daten mit der auf Blatt 3 Aufgabe 1 entwickelten readData Funktion einliest, sortiert und das Ergebnis mit writeData ausgibt.
Messen Sie das Laufzeitverhalten der verschiedenen Sortierverfahren für 100, 1000 und 10000 Zahlen.
Tip: Es lohnt sich, für die Generieung der Testmengen ein Programm zu schreiben.
Sind die Sortierverfahren stabil? Geben Sie zu jedem Verfahren eine Begründung an.

Aufgabe 2 [20 Punkte]

Implementieren Sie eine Funktion zur Lösung des Traveling Salesman Problems. Überlegen Sie sich zunächst die nötigen Datenstrukturen. Lesen Sie dann die Daten des Baumen aus einer Datei, die wie folgt aufgebaut ist, ein:
```
\Anzahl_Knoten\
\Knoten1_von_Kante\ \Knoten2_nach_Kante\ \Kantengewicht\
\Knoten1_von_Kante\ \Knoten2_nach_Kante\ \Kantengewicht\
 ...
\Knoten1_von_Kante\ \Knoten2_nach_Kante\ \Kantengewicht\
      
```
Berechnen Sie den kürzesten Weg und geben Sie das Ergebnis wieder in eine Datei aus, die wie folgt aufgebaut ist:
```
\StartKnoten\ ... \EndKnoten\ \Gesamtlänge\
      
```
Überlegen Sie, welchen Aufwand der Algorithmus größenordnungsmäßig hat und begründen Sie.

Last modified: Wed Nov 15 13:34:53 MET 1995