Prof. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 1. Februar 2005
Christian Ehrhardt Blatt 12






Allgemeine Informatik 3 (WS 2004/2005)


Abgabetermin 15.02.2005

Sortieren (20 Punkte)

In diesem Blatt sollen die Einträge in einer Datenbank, wie sie im letzten Blatt bereits verwendet wurde, sortiert werden. Dabei sollen keine temporären Dateien oder ähnliches verwendet werden und es sollen nicht mehr als 5 Einträge gleichzeitig im Speicher sein. Es ist also nicht möglich, die gesamte Datenbank einzulesen, zu sortieren und dann wieder als ganzes in die Datei zu schreiben.

Vergleichen von Einträgen

Der Einfachheit halber, sollen Datenbankeinträge immer zunächst nach dem ersten Datenfeld verglichen werden. Wenn dabei zwei Einträge gleich sind, dann soll das zweite Datenfeld herangezogen werden, dann das dritte usw.

Quicksort (10 Punkte)

Implementiert den aus Allgemeine Informatik bekannten Quicksort-Algorithmus, für eine solche Datenbankdatei. Eine Beschreibung des Quicksort-Algorithmus findet sich zum Beispiel im Skript zu Allgemeine Informatik I aus dem Sommersemester 2004. Das entsprechende Kapitel ist online verfügbar unter http://www.mathematik.uni-ulm.de/sai/ss04/prog/slides/rekursion.html

Bubblesort (10 Punkte)

Implementiert den Bubblesort-Algorithmus für eine solche Datenbankdatei. Bei Bubblesort soll es möglich sein, daß mehrere Prozesse gleichzeitig an der Sortierung der Datei arbeiten. Damit dabei kein Durcheinander entsteht, müssen sich die Prozesse mit Hilfe von lockf synchronisieren. Dabei soll natürlich immer nur der im Moment benötigte Teil der Datei gesperrt werden.

Hinweis

In seltenen Fällen kann es auf einem NFS-Dateisystem zu Problemen mit lockf kommen. Da sich auch Eure Heimatverzeichnisse auf einem solchen Dateisystem befinden, empfiehlt es sich, im Falle von Problemen die Datenbank in einem lokalen Verzeichnis (z.B. /tmp) abzulegen.