Robert Sedgewick: Algorithmen

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


8. Elementare Sortierverfahren



Distribution Counting

Eine sehr spezielle Situation, für die ein einfacher Sortieralgorithmus existiert, ist folgende: »Sortiere eine Datei von N Datensätzen, deren Schlüssel voneinander verschiedene ganze Zahlen zwischen 1 und N sind.« Dieses Problem kann gelöst werden, indem ein temporäres Feld t mit der Anweisung for i:=1 to N do t[a[i]]:= a[i] verwendet wird. (Wie wir oben gesehen haben, ist es auch möglich, wenn auch komplizierter, dieses Problem ohne ein Hilfsfeld zu lösen.)

Ein realistischeres Problem der gleichen Art ist: »Sortiere eine Datei von N Datensätzen, deren Schlüssel ganze Zahlen zwischen 0 und M - 1 sind.« Falls M nicht zu groß ist, kann ein Distribution Counting (Verteilungszählen) genannter Algorithmus benutzt werden, um dieses Problem zu lösen. Die Idee besteht darin, die Anzahl der Schlüssel mit jedem Wert zu ermitteln und dann die Ergebnisse der Zählung zu verwenden, um bei einem zweiten Durchlauf durch die Datei wie im folgenden Programm die Datensätze in die richtige Position zu bringen:

 
    for j:=0 to M-1 do count[j]:=0;
    for i:=1 to N do
      count[a[i]]:=count[a[i]]+1;
    for j:=1 to M-1 do
      count[j]:=count[j-1]+count[j];
    for i:=N downto 1 do
      begin
      b[count[a[i]]]:=a[i];
      count[a[i]]:=count[a[i]]-1
      end;
    for i:=1 to N do a[i]:=b[i];

Um zu sehen, wie dieses Programm arbeitet, betrachten wir das Beispiel einer Datei von Buchstaben (die wir wie eingangs erwähnt intern durch ganze Zahlen darstellen) in der obersten Zeile der Abbildung 8.11. Die erste for-Schleife initialisiert die Elemente von count mit 0; die zweite setzt count[1]=6, count[2]=4, count[3]=1 und count[4]=4, da sechs A, vier B usw. vorhanden sind. Die dritte for-Schleife addiert diese Zahlen auf und erzeugt count[1]=6, count[2]=10, count[3]=11 und count[4]=15. Das besagt, es gibt sechs Schlüssel, die kleiner oder gleich A sind, zehn Schlüssel, die kleiner oder gleich B sind usw.

Abbildung 8.11
Abbildung 8.11 Distribution Counting.

Diese können nun als Adressen benutzt werden, um das Feld zu sortieren, wie die Abbildung zeigt. Das ursprünglich eingegebene Feld a ist auf der obersten Zeile dargestellt; der Rest der Abbildung zeigt, wie das temporäre Feld b gefüllt wird. Wenn zum Beispiel das A am Ende der Datei vorgefunden wird, wird es auf den Platz 6 gesetzt, da count[1] besagt, daß es sechs Schlüssel gibt, die kleiner oder gleich A sind. Danach wird count[1] dekrementiert, da die Zahl der Schlüssel, die kleiner oder gleich A sind, sich nun um eins verringert hat. Dann wird das D von der vorletzten Position in der Datei auf den Platz 14 gesetzt, und count[4] wird dekrementiert, usw. Die innere Schleife läuft von N rückwärts bis 1, so daß der Sortiervorgang stabil ist. (Der Leser kann dies nachprüfen.)

Dieses Verfahren ist für den betrachteten Typ von Dateien sehr gut geeignet. Außerdem kann aus ihm eine noch wesentlich leistungsfähigere Methode entwickelt werden, die wir in Kapitel 10 untersuchen.


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