Sortieren

Mit die wichtigste Funktion, die DatenBank-Managementsysteme (DBMS) ist das Sortieren von Daten nach bestimmten, vom Benutzer vorgegebenen Kriterien. Delphis Komponenten für StringLists haben zwar die Eigenschaft sorted, sortieren dabei aber Listeneinträge nur alphabetisch. Was macht man z.B., wenn man eine Datei nach dem Alter oder der Gehaltsgruppe sortieren möchte?

Ein klassisches Sortierverfahren zum Sortieren z.B. eines Stapels von Spielkarten basiert auf der folgenden Idee:

Vergleiche die oberste und die zweite Karte. Ist der Wert der zweiten Karte größer als der der ersten, vertausche beide, wenn nicht gehe gleich zum nächsten Schritt
Vergleiche die zweite und die dritte Karte und vertausche ggf. (s.o.) ihre Reihefolge
...
...
Vergleiche die vorletzte und die letzte Karte miteinander und vertausche ggf.
Wiederhole das Spiel, nimm allerdings die letzte Karte aus dem Spiel, sie hat bereits den kleinsten Wert.

In den Spalten der folgenden Tabelle kann man die Entwicklung dieses Algorithmus anhand von 5 Zahlen (jeweils in einer Spalter der Tabelle) verfolgen:

Die Anzahl der Vergleiche (und ggf. Vertauschungen) beträgt im obigen Beispiel 4+3+2+1 = 10. Allgemein muss man bei diesem Verfahren (n-1) + (n-2) +(n-3) + ... + 1 = 0,5*n*(n-1) Vergleiche anstellen, um die Liste zu sortieren. D.h. die Anzahl der Operationen zum Sortieren einer Liste wächst quadratisch mit der Anzahl der Einträge, eine Tatsache, die sich vor allem beim Sortieren längerer Listen unangenehm bemerkbar macht. Es gibt zwar Verfahren, die ein wenig schneller sind, allerdings bleibt es bei der Tatsache, dass Sortieren eine sehr zeitaufwendige Aufgabe ist.

Die folgende Prozedur lässt erkennen, wie man den o.a. Sortieralgotithmus in Pascal implementieren kann:

procedure Sortiere;
var n,m,zw : integer;
begin
for n := 1 to 5-1 do             // n = 5 : Anzahl der Zahlen
    for m := 1 to 5-n do begin
      if zahlen[m] < zahlen[m+1] then begin
      zw := zahlen[m+1];           // zw als Zwischenspeicher
      zahlen[m+1] := zahlen[m];
      zahlen[m] := zw;
    end;
end;
end;

Datensätze einer Personendatei enthalten nomalerweise verschiedene Einträge (Felder), nach denen ein Sortieren erfolgen soll. Die obige Sortier-Routine lässt sich allerdings sehr einfach auf solche Sortiervorgänge übertragen: Man muss nur das Entscheidungskriterium ändern. Es sei jetzt datei : array[1..5] of TDatensatz. Jeder Datensatz enthält wie vorher die Informationen name. vorname und alter.

procedure SortiereNachNamen;
var n,m : integer;
    zwds : TDAtenSatz;
begin
for n := 1 to 5-1 do             // n = 5 : Anzahl der Datensätze
    for m := 1 to 5-n do begin
      if datei[m].name < datei[m+1].name then begin
      zwds := datei[m+1];           // zwds als Zwischenspeicher
      datei[m+1] := datei[m];
      datei[m] := zwds;
    end;
end;
end;

Aufgaben

Erweitere das Programm datei2.pas um die fehlenden Routinen bzw. erweitere Deine eigene Datenbank um die Optionen 'Sortieren' und 'Filtern'.