Robert Sedgewick: Algorithmen

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


10. Digitales Sortieren



Straight Radix Sort

Ein anderes digitales Sortierverfahren besteht darin, die Bits von rechts nach links zu betrachten. Das ist die Methode, die von den alten Lochkarten-Sortiermaschinen benutzt wurde: Ein Stoß Karten durchlief achtzigmal die Maschine, für jede Spalte einmal, wobei von rechts nach links vorgegangen wurde. Abbildung 10.4 zeigt, wie ein von rechts nach links bitweise vorgehendes digitales Sortierverfahren für unsere Datei von Beispielschlüsseln abläuft. Die i-te Spalte in Abbildung 10.4 ist bereits nach den letzten i Bits der Schlüssel sortiert; sie wird aus der (i-1)-ten Spalte abgeleitet, indem erst alle Schlüssel mit einer 0 im i-ten Bit und dann alle Schlüssel mit einer 1 im i-ten Bit extrahiert werden.

Abbildung 10.4
Abbildung 10.4 Straight Radix Sort (digitales Sortieren »von rechts nach links«).

Es ist nicht leicht, sich davon zu überzeugen, daß diese Methode funktioniert; tatsächlich funktioniert sie überhaupt nur dann, wenn der Ein-Bit-Zerlegungsprozeß stabil ist. Nachdem festgestellt worden ist, daß die Stabilität wesentlich ist, kann ein einfacher Beweis dafür angegeben werden, daß die Methode funktioniert: Nachdem die Schlüssel mit dem i-ten Bit 0 vor denen mit dem i-ten Bit 1 angeordnet worden sind (in stabiler Weise), wissen wir, daß zwei beliebige Schlüssel in der richtigen Reihenfolge (auf der Basis der bereits betrachteten Bits) in der Datei angeordnet sind, entweder weil ihre i-ten Bits verschieden sind, wobei sie in diesem Falle durch das Zerlegen in die richtige Reihenfolge gebracht werden, oder weil ihre i-ten Bits gleich sind, wobei sie sich in diesem Falle auf Grund der Stabilität in der richtigen Reihenfolge befinden. Die Forderung der Stabilität bedeutet zum Beispiel, daß die Zerlegungsmethode, die bei Radix Exchange Sort angewandt wurde, für dieses von rechts nach links vorgehende Sortierverfahren nicht benutzt werden kann.

Das Zerlegen gleicht dem Sortieren einer Datei mit nur zwei Werten, und das Sortierverfahren des Distribution Countings aus Kapitel 8 ist hierfür vorzüglich geeignet. Wenn wir annehmen, daß im Programm des Distribution Countings M = 2 gilt, und wenn wir a[i] durch bits (a[i],k,1) ersetzen, so wird dieses Programm zu einer Methode für das Sortieren der Elemente des Feldes a nach dem k-ten Bit von rechts und die Speicherung des Ergebnisses in einen temporären Feld t. Es gibt jedoch keinen Grund, M = 2 zu benutzen; in Wirklichkeit sollten wir M so groß wie möglich wählen, wobei wir jedoch berücksichtigen müssen, daß wir eine Tabelle von M Zählungen benötigen. Dies entspricht der gleichzeitigen Verwendung von m Bits während des Sortierens, mit M = 2m. Somit ergibt sich, daß Straight Radix Sort kaum mehr als eine Verallgemeinerung des Distribution Counting-Sortierverfahrens ist, wie in der folgenden Implementation für das Sortieren von a[1..N] nach den w am weitesten rechts befindlichen Bits:

    procedure straightradix;
      var i,j,pass: integer;
          count: array[0..M] of integer;
      begin
      for pass:=0 to (w div m)-1 do
        begin
        for j:=0 to M-1 do count[j]:=0;
        for i:=1 to N do
          count[bits(a[i],pass*m,m)]:=count[bits(a[i],pass*m,m)]+1;
        for j:=1 to M-1 do
          count[j]:=count[j-1]+count[j];
        for i:=N downto 1 do
          begin
          b[count[bits(a[i],pass*m,m)]]:=a[i];
          count[bits(a[i],pass*m,m)]:=count[bits(a[i],pass*m,m)]-1;
          end;
        for i:=1 to N do a[i]:=b[i];
        end;
      end;

Der Klarheit wegen verwendet diese Prozedur zwei Aufrufe von bits, um count zu inkrementieren und zu dekrementieren, obwohl einer genügen würde. Auch wurde der Zusammenhang M = 2m in den Variablennamen beibehalten, obwohl manche Varianten von Pascal nicht zwischen m und M unterscheiden können.

Die obige Prozedur läuft nur dann einwandfrei ab, wenn w ein Vielfaches von m ist. Normalerweise ist das keine besonders einschränkende Voraussetzung für das digitale Sortieren; es entspricht einfach der Aufteilung der zu sortierenden Schlüssel in eine ganzzahlige Anzahl von gleich großen Teilen. Wenn m = w gilt, ergibt sich das Distribution Counting-Sortieren; für = 1 erhält man Straight Radix Sort, das von rechts nach links vorgehende, bitweise digitale Sortierverfahren, das im obigen Beispiel beschrieben wurde.

Die obige Implementation bewegt die Datei während jeder Phase des Distribution Countings von a nach b und anschließend in einer einfachen Schleife zurück zu a. Wenn man wollte, könnte man diese »Feldkopier«-Schleife beseitigen, indem man zwei Kopien des Distribution Counting-Codes erzeugt, eine zum Sortieren von a nach b und die andere zum Sortieren von b nach a.


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