Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


8. Elementare Sortierverfahren



Sortieren von Dateien mit großen Datensätzen

Es ist möglich (und wünschenswert), es so einzurichten, daß jedes Sortierverfahren nur N »Austauschoperationen« von vollständigen Datensätzen ausführt, indem man den Algorithmus indirekt (unter Verwendung eines Feldes von Indizes) mit der Datei arbeiten und das Umordnen dann nachträglich vornehmen läßt.

Insbesondere dann, wenn das Feld a[1..N] aus umfangreichen Datensätzen besteht, ziehen wir es vor, mit einem »Zeigerfeld« p[1..N] zu arbeiten, wobei ein Zugriff auf das Originalfeld nur für Vergleiche erfolgt. Wenn wir am Anfang p[i]=i definieren, brauchen die obigen Algorithmen (wie auch alle Algorithmen in nachfolgenden Kapiteln) nur in der Weise modifiziert zu werden, daß die Bezeichnung a[p[i]] statt a[i] benutzt wird, wenn a[i] in einem Vergleich verwendet wird, und daß p statt a benutzt wird, wenn Daten bewegt werden. Dadurch wird ein Algorithmus erzeugt, der das Indexfeld in der Weise »sortiert«, daß p[1] der Index des kleinsten Elements in a ist, p[2] der Index des zweitkleinsten Elements in a usw., und die Kosten, die bei einem unnötigen Hin- und Herbewegen großer Datensätze entstehen würden, werden vermieden. Das folgende Programm zeigt, wie Insertion Sort modifiziert werden könnte, damit es in dieser Weise abläuft.

    procedure insertion;
      var i,j,v: integer;
      begin
      for i:=1 to N do p[i]:=i;
      for i:=2 to N do
        begin
        v:=p[i]; j:=i;
        while a[p[j-1]]>a[v] do
          begin p[j]:=p[j-1]; j:=j-1 end;
        p[j]:=v
        end
      end;

In diesem Programm erfolgt ein Zugriff auf das Feld a nur, um die Schlüssel von zwei Datensätzen zu vergleichen. Daher könnte es leicht dahingehend abgeändert werden, daß es Dateien mit sehr umfangreichen Datensätzen behandeln kann, indem der Vergleich derart modifiziert wird, daß der Zugriff nur auf einen kleinen Teil eines umfangreichen Datensatzes erfolgt oder indem der Vergleich durch eine kompliziertere Prozedur realisiert wird. Abbildung 8.6 zeigt, wie dieser Prozeß eine Permutation erzeugt, die die Reihenfolge angibt, in der ein Zugriff auf die Elemente des Feldes erfolgen kann, damit eine sortierte Liste definiert wird. Für viele Anwendungen ist dies ausreichend (die Daten brauchen möglicherweise gar nicht bewegt zu werden). Zum Beispiel könnte man die Daten in sortierter Reihenfolge ausdrucken, indem man wie im Sortierfahren selbst einfach indirekt über das Indexfeld auf sie verweist.

Abbildung 8.6
Abbildung 8.6 Umordnen eines »sortierten« Feldes.

Doch was ist zu tun, wenn die Daten tatsächlich umgeordnet werden müssen, wie in der untersten Zeile der Abbildung 8.6? Wenn genug zusätzlicher Speicherplatz für eine weitere Kopie des Felds zur Verfügung steht, ist das unbedeutend, doch wie steht es mit der häufiger auftretenden Situation, wenn nicht genügend Platz für eine weitere Kopie der Datei vorhanden ist?

In unserem Beispiel befindet sich das erste A an seiner richtigen Position, mit p[1]=1, so daß nichts mit ihm getan werden muß. Das erste, was wir tun möchten, ist, den Datensatz mit dem nächstgrößeren Schlüssel (den mit dem Index p[2]) auf die zweite Position in der Datei zu setzen. Doch vorher müssen wir den Datensatz speichern, der sich auf dieser Position befindet, sagen wir in t. Nachdem wir nun diese Bewegung ausgeführt haben, können wir annehmen, daß sich in der Datei auf der Position p[2] ein »Loch« befindet. Doch wir wissen, daß der Datensatz auf der Position p[p[2]] letztendlich dieses Loch ausfüllen sollte. Indem wir in dieser Art fortfahren, gelangen wir schließlich an den Punkt, wo wir das Element benötigen, das sich ursprünglich auf der zweiten Position befand und das wir in t aufbewahrt haben. In unserem Beispiel führt dieser Prozeß zu der Reihe von Zuweisungen t:=a[2]; a[2]:=a[11]; a[11]:=a[13]; a[13]:=a[2]; a[2]:=t. Diese Zuweisungen transportieren die Datensätze mit den Schlüsseln A, P und S auf ihren richtigen Platz in der Datei, was gekennzeichnet werden kann, indem p[2]=2, p[11]=11 und p[13]=13 gesetzt wird. (Jedes Element mit p[i]=i befindet sich an seinem Platz und braucht nicht wieder berührt zu werden.) Nun kann dieser Prozeß für das nächste Element, welches nicht an seinem Platz ist, erneut ablaufen usw., und so wird letztlich die gesamte Datei umgeordnet, wobei jeder Datensatz nur einmal bewegt wird, wie im folgenden Programm:

    procedure insitu;
      var i,j,k,t: integer;
      begin
      for i:=1 to N do
        if p[i]<>i then
          begin
          t:=a[i]; k:=i;
          repeat
            j:=k; a[j]:=a[p[j]]; 
            k:=p[j]; p[j]:=j; 
          until k=i;
          a[j]:=t
          end;
      end;

Die Eignung dieser Methode für spezielle Anwendungen hängt natürlich von der relativen Größe der Datensätze und Schlüssel in der zu sortierenden Datei ab. Sicher würde man für eine aus kleinen Datensätzen bestehende Datei wegen des erforderlichen zusätzlichen Platzes für das Indexfeld und der zusätzlich benötigten Zeit für die indirekten Vergleiche nicht so viel Aufwand treiben. Für Dateien jedoch, die aus großen Datensätzen bestehen, ist es fast immer wünschenswert, ein indirektes Sortieren vorzunehmen, und in vielen Anwendungsfällen müssen die Daten eventuell überhaupt nicht bewegt werden. Natürlich ist für Dateien mit sehr umfangreichen Datensätzen wie oben erläutert einfaches Selection Sort die anzuwendende Methode.

Aufgrund der Existenz dieser indirekten Vorgehensweise sind die Schlußfolgerungen, die wir in diesem Kapitel und in den nachfolgenden ziehen, wenn wir Methoden des Sortierens von Dateien aus ganzen Zahlen vergleichen, sicher auf allgemeinere Situationen anwendbar.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]