Claus Schönleber

Hitchhacker´s Guide To PASCAL  [Vol. 2]
[ zurück ]
   [ Start | Beispielprogramme Download | Home ]

Inhalt

Typisierte 
 Konstanten
Sets (Mengen)
Rekursion
Records
Dateien
 (Random Access)
Pointer
Algorithmen
- Hashing
- Sortieren
 		  

Sortieren

In Kurs 1 wurde schon einiges über das Sortieren gesagt. Am Beispiel des Verfahrens "Bubblesort" (Beispielprogramme) wurde gezeigt, wie man ein Feld auf einfache Weise in die gewünschte Reihenfolge ordnen kann. Die Grundoperation war Tauschen zweier Variablen (Feldelemente). Das Beispiel, da es eine Funktionsdemonstration ist, zeigt nicht, wie die Datensätze aussehen, die im Alltag zur Sortierung anstehen. Die können sehr viel komplexer sein, als die Zahlenliste im erwähnten Beispiel. Nehmen wir als Beispiel nur eine Personaldatei. Da besteht ein Datensatz aus Name, Vorname, Straße, Postleitzahl, Ort, Telefonnummer und vielen anderen Daten. Wenn die Tauschoperation hier ansetzen müßte, hätte das Programm nicht nur viel, sondern auch Unnötiges zu tun. Denn anstatt die Datensätze wirklich zu tauschen kann man sich ja notieren, wo sie eigentlich stehen müßten.

Dieser Trick wird "indizierte Datei" oder manchmal auch, nicht exakt, "ISAM-Datei" (Indexsequentielle Datei) genannt. Er ist aber eine Vorstufe zur ISAM-Datei.

Indizierte Dateien

Um eine zu sortierende Liste zu indizieren, benötigt man eine weitere Liste, in der die Indices (Positionen) der einzelnen Datensätze nach der Reihenfolge ihrer Eingabe eingetragen werden. Will man die Datensätze sortieren, so greift man beim Vergleich während des Sortierens nicht direkt auf die Datensätze zu, sondern über die in der Indexliste eingetragenen Positionen. Die Listen können Arrays sein (wie im Beispiel) oder auch Dateien. Dabei ist das indizierte Sortieren vom verwendeten Sortierverfahren unabhängig, denn die Indizierung regelt ja nur den Zugriffsmechanismus. 
PROGRAM index_sort;

  TYPE person = RECORD 
                  name,
                  vorname : STRING;
                  gehalt  : real;
                END;

  VAR data    : ARRAY [1..10] OF person;
      index   : ARRAY [1..10] OF integer;
      swapped : boolean;
      i       : integer;

PROCEDURE swap (VAR x,y : integer);
  VAR dummy : integer;
BEGIN
  dummy := x;
  x := y;
  y := dummy;
END;

BEGIN
  (*** Initialisierung des Feldes durch Eingabe ***)
  (*** über die Tastatur ***)
    FOR i := 1 TO 10 DO
    BEGIN
      WITH data [i] DO
      BEGIN
        write ('Name: ');
        readln (name);
        write ('Vorname: ');
        readln (vorname);
        write ('Gehalt (DM): ');
        readln (gehalt);
        (*** Neuen Index in Indexliste eintragen ***)
          index [i] := i;
      END;
    END;
  (*** Sortieralgorithmus Bubblesort ***)
    REPEAT
      swapped := false; (* Flag initialisieren *)
      FOR i := 1 TO 9 DO
      BEGIN
        IF (data [index [i]] > data [index [i + 1]]) THEN
        BEGIN
          (*** Es wird jetzt der Index getauscht, ***)
          (*** nicht der Datensatz! ***)
            swap (index [i],index [i + 1]);
          swapped := true;
        END;
      END;
    UNTIL NOT swapped;
  (*** Ausgabe des sortierten Feldes ***)
    FOR i := 1 TO 10 DO
      writeln (data [index [i]]);
END.
Der Sortiervorgang. Da beim Sortieren die Datensätze nicht bewegt wurden, sieht die Liste selbst nach wie vor ungeordnet aus. Der Inhalt der Indexliste hat sich dabei aber verändert; wird die Indexliste jetzt nämlich der Reihe nach durchgesehen, findet man in jeder Komponente dieser Liste den Index des Datensatzes, der als nächster kommt. Damit ist die Liste sortiert, wenn man über diese Indexliste zugreift, sonst nicht!

Der Vorteil ist offensichtlich. 

  1. Erstens müssen beim Tauschvorgang nicht sämtliche Datenfelder ausgetauscht werden. Das Sortieren geht damit wesentlich schneller, vor allem, wenn man auf einer Platte sortiert.
  2. Zweitens kann man jetzt plötzlich eine einzige Datei (Liste) nach mehreren Kriterien gleichzeitig sortieren, indem man für jedes Kriterium eine eigene Indexliste (Indexdatei) anlegt. Dadurch spart man sich sehr viel Zeit und dem "Rechenknecht" sehr viel Arbeit, wenn man eine Liste nach anderen Kriterien sortiert ausgeben will.

Zwei andere Sortierverfahren

Damit Sie nicht nur auf Bubblesort angewiesen sind, sollen hier noch zwei weitere nicht allzu schwierige Algorithmen besprochen werden.

Dummsort

Der Name ist von mir. Er läuft im Gegensatz zu Bubblesort eine konstante Zeit, also unabhängig vom Sortierungsgrad. Man könnte ihn als Mischung aus Bubblesort und "Direktem Auswählen" betrachten.

Ausgehend von einer Liste mit n Elementen kann man folgendes Fragment formulieren: 

FOR i := 1 TO n - 1 DO
  FOR j := i + 1 TO n DO
  BEGIN
    IF a[i] > a[j] THEN
      swap (a[i],a[j]);
  END;

Direktes Auswählen (Straight Selection)

Es ist hier gleich als Prozedur formuliert, die sofort in ein Programm eingebunden werden kann ("feld" muß natürlich ein geeigneter Arraytyp sein). Es ist wesentlich schneller als Bubblesort und kann in Programmen durchaus als akzeptabel schnelle Sortierroutine verwendet werden. 
PROCEDURE sort (VAR f : feld);
  VAR i,j,k,x : integer;
BEGIN
  FOR i := 1 TO (n - 1) DO
  BEGIN
    k := i;
    x := f [i];
    FOR j := (i + 1) TO n DO
      IF (f [j] < x) THEN
      BEGIN
        k := j;
        x := f [j];
      END;
    f [k] := f [i];
    f [i] := x;
  END;
END;
Für dieses Verfahren möchte ich auch gleich eine Version zum Sortieren von Random Access Dateien zeigen. Das Verfahren sortiert direkt auf der Platte. Ob Sie normal oder indiziert sortieren wollen, ist von Fall zu Fall zu entscheiden. Hier die normale Version. "workfiletype" ist eine Datei mit einem Recordtyp, der ein Feld "key", das Schlüsselfeld, enthält. Das ist der Name oder die Kundennummer. Es wird bei Bedarf anders genannt. In die Prozedur ist weiterhin ein Bildschirmteil eingebaut, der mit Hilfe einer einfachen Balkengraphik anzeigt, wieviel Prozent der Datei schon sortiert worden sind.

Der folgende Quelltext ist ein Fragment, das zu einem übersetzbaren Programm noch ergänzt werden muß: 

  VAR workfiletype = FILE OF ....;
      str255       = STRING;

PROCEDURE file_sort (VAR _file : workfiletype);
  CONST twentyblanks = '                    ';
  VAR i,j,k,fs,p,ii,jj,kk : integer;
      ai,aj,ak,x          : indexdata;
      w1,w2 : str255;

(*** Um auch kleingeschriebenes richtig ***)
(*** alphabetisch zu sortieren... ***)
FUNCTION convert_up (x : str255) : str255;
  VAR i : integer;
BEGIN
  FOR i := 1 TO length (x) DO
    x [i] := upcase (x [i]);
  convert_up := x;
END; (*** of convert_up ***)

BEGIN
  clrscr;
  writeln ('Datei wird sortiert...');
  writeln;
  writeln;
  writeln (' 0 % 100');
  writeln (' ------------------------------');
  assign (_file,index_name);
  reset (_file);
  (*** Ermittle die Dateigröße ***)
    fs := filesize (indexfile);
  FOR i := 0 TO (fs - 2) DO
  BEGIN
    (*** Bildschirmzauber ***)
      (*** Angabe in Prozent... ***)
        write (^M,twentyblanks,(100 * i / fs):3:0,'%');
      (*** Male den Balken entsprechend lang... ***)
        FOR p := 1 TO trunc (((100 * i) / fs) / 10) DO
          write ('*');
    (*** Hier beginnt das Sortieren ***)
      k := i;
      (* x := a [i]; *)
        seek (_file,i);
        read (_file,ai);
        x := ai;
      FOR j := (i + 1) TO (fs - 1) DO
      BEGIN
        (* hole aj *)
          seek (_file,j);
          read (_file,aj);
        w1 := convert_up (aj.key);
        w2 := convert_up (x.key);
        IF (w1 < w2) THEN
        BEGIN
          k := j;
          (* x := a [j]; *)
            x := aj;
        END;
      END;
      (* a [k] := a [i]; *)
        seek (_file,k);
        write (_file,ai);
      (* a [i] := x; *)
        seek (_file,i);
        write (_file,x);
  END;
  close (_file);
  write (^M,twentyblanks,'100% ');
  FOR p := 1 TO 10 DO
    write ('[[[');
  gotoxy (29,20);
  write ('--- Taste drcken ---');
  REPEAT
  UNTIL keypressed;
  clrscr;
END; (*** of sort ***)

Weiter Links zum Thema "Sortieren":

[Ende Teil 2]
[ zurück ]
    (c) 2001 Schoenleber.com