Robert Sedgewick: Algorithmen

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


10. Digitales Sortieren



Radix Exchange Sort

Nehmen wir an, daß wir die Datensätze einer Datei so umordnen können, daß alle die Datensätze, deren Schlüssel mit einem Bit 0 beginnen, vor all denen kommen, deren Schlüssel mit einem Bit 1 beginnen. Hierdurch wird unmittelbar eine rekursive Sortiermethode definiert: Wenn die beiden Teildateien unabhängig voneinander sortiert werden, ist die ganze Datei sortiert. Das Umordnen (der Datei) erfolgt in einer Weise, die dem Zerlegen bei Quicksort sehr ähnlich ist: Durchsuche die Datei von links, bis ein Schlüssel gefunden wird, der mit einem Bit 1 beginnt, durchsuche sie von rechts, bis ein Schlüssel gefunden wird, der mit einem Bit 0 beginnt, tausche die Schlüssel aus und setze diesen Prozeß so lange fort, bis sich die Zeiger des Durchsuchens treffen. Dies führt zu einem rekursiven Sortierverfahren, das große Ähnlichkeit mit Quicksort besitzt:

    procedure radixexchange(l,r,b: integer);
      var t,i,j: integer;
      begin
      if (r>l) and (b>=0) then
        begin
        i:=l; j:=r;
        repeat
          while (bits(a[i],b,1)=0) and (i<j) do i:=i+1;
          while (bits(a[j],b,1)=1) and (i<j) do j:=j-1;
          t:=a[i]; a[i]:=a[j]; a[j]:=t;
        until j=i;
        if bits(a[r],b,1)=0 then j:=j+1;
        radixexchange(l,j-1,b-1);
        radixexchange(j,r,b-1);
        end
      end;

Nehmen wir der Einfachheit halber an, daß a[1..N] positive ganze Zahlen enthält, die kleiner als 232 sind (so daß sie als Binärzahlen mit 32 Bits dargestellt werden können). Dann bewirkt radixexchange (1, N, 31) das Sortieren des Feldes. Die Variable b gibt das gerade untersuchte Bit an und läuft von 31 (ganz links) rückwärts bis 0 (ganz rechts). (Normalerweise ist es möglich, die Implementation von bits an die Maschinendarstellung negativer Zahlen anzupassen, so daß negative Zahlen beim Sortieren in gleicher Weise behandelt werden.)

Diese Implementation besitzt offensichtlich große Ähnlichkeit mit der rekursiven Implementation von Quicksort in Kapitel 9. Seinem Wesen nach gleicht das Zerlegen bei Radix Exchange Sort dem Zerlegen bei Quicksort, abgesehen davon, daß anstelle einer bestimmten Zahl aus der Datei die Zahl 2b als das zerlegende Element verwendet wird. Da 2b möglicherweise nicht in der Datei enthalten ist, kann es keine Garantie dafür geben, daß ein Element während des Zerlegens auf seinen endgültigen Platz gesetzt wird. Weiterhin können wir, da jeweils nur ein Bit untersucht wird, uns nicht auf Marken verlassen, um das Durchsuchen mit den Zeigern abzubrechen; daher wurden die Tests (i<j) in die Schleifen des Durchsuchens eingebaut. Wie bei Quicksort wird für den Fall j = i ein zusätzlicher Austausch vorgenommen, doch es ist nicht erforderlich, diesen Austausch außerhalb der Schleife rückgängig zu machen, da a[i] mit sich selbst »ausgetauscht« wird. Die Zerlegung bricht ab, wenn j = i gilt und alle Elemente rechts von a[i] an der b-ten Stelle ein Bit 1 und alle Elemente links von a[i] an der b-ten Stelle ein Bit 0 haben. Das Element a[i] selbst hat ein Bit 1, außer wenn alle Schlüssel in der Datei an der b-ten Stelle eine 0 aufweisen. Die obige Implementation besitzt einen zusätzlichen Test unmittelbar nach der Schleife für die Zerlegung, um diesen Fall zu berücksichtigen.

Abbildung 10.1 zeigt, wie unsere aus Schlüsseln bestehende Beispieldatei mittels dieser Methode zerlegt und sortiert wird. Sie kann mit Abbildung 9.3 für Quicksort verglichen werden, obwohl die Arbeitsweise der Zerlegungsmethode ohne die Binärdarstellung der Schlüssel völlig undurchsichtig ist.

Abbildung 10.1
Abbildung 10.1 Teildateien bei Radix Exchange Sort.

Abbildung 10.2 zeigt die Zerlegung anhand der Binärdarstellung der Schlüssel. Es wird ein einfacher, aus fünf Bits bestehender Code angewandt, wobei der i-te Buchstabe des Alphabets durch die Binärdarstellung der Zahl i bezeichnet wird. Dies ist eine vereinfachte Variante eines realen Zeichencodes, bei dem mehr Bits (sieben oder acht) verwendet und mehr Zeichen (Groß- und Kleinbuchstaben, Ziffern, Sonderzeichen) dargestellt werden. Durch das Übertragen der Schlüssel in Abbildung 10.1 in diesen Zeichencode aus fünf Bits, durch das Verdichten der Tabelle in der Weise, daß das Zerlegen der Teildateien »parallel« anstatt zeilenweise gezeigt wird, und durch anschließendes Vertauschen von Zeilen und Spalten können wir anhand von Abbildung 10.2 zeigen, wie die führenden Bits der Schlüssel die Zerlegung steuern. In dieser Abbildung wird jede Zerlegung durch eine weiße »0«-Teildatei angegeben, der eine graue »1«-Teildatei im nächsten Diagramm rechts von ihr folgt, Teildateien vom Umfang 1 scheiden allerdings dort, wo sie auftreten, aus dem Zerlegungsprozeß aus.

Abbildung 10.2
Abbildung 10.2 Radix Exchange Sort (digitales Sortieren »von links nach rechts«).

Ein ernsthaftes potentielles Problem für das digitale Sortieren, das in diesem Beispiel nicht zum Ausdruck kommt, besteht darin, daß entartete Zerlegungen (Zerlegungen, bei denen alle Schlüssel für das verwendete Bit den gleichen Wert haben) häufig auftreten können. Diese Situation entsteht gewöhnlich in realen Dateien, wenn kleine Zahlen (mit vielen führenden Nullen) sortiert werden. Sie tritt auch bei Zeichen auf: Nehmen wir zum Beispiel an, daß für je vier Zeichen Schlüssel mit 32 Bits gebildet werden, indem jedes Zeichen mit Hilfe eines standardmäßigen Acht-Bit-Codes verschlüsselt wird und diese Codes dann zusammengesetzt werden. Dann ist das Auftreten von entarteten Zerlegungen zu Beginn jeder Zeichenposition wahrscheinlich, da beispielsweise Kleinbuchstaben in den meisten Zeichencodes alle mit den gleichen Bits beginnen. Viele ähnliche Effekte müssen offenbar beim Sortieren derartig kodierter Daten in Betracht gezogen werden.

Aus Abbildung 10.2 ist ersichtlich, daß, nachdem ein Schlüssel anhand seiner linken Bits von allen anderen Schlüsseln unterschieden worden ist, keine weiteren Bits von ihm betrachtet werden. In einigen Situationen ist das ein deutlicher Vorteil, in anderen ein Nachteil. Wenn die Schlüssel wirklich zufällige Bits sind, müßte sich jeder Schlüssel nach ungefähr lg N Bits von den anderen unterscheiden, was wesentlich weniger sein könnte als die Anzahl der Bits in den Schlüsseln. Dies liegt daran, daß in einer zufälligen Situation damit zu rechnen ist, daß jede Zerlegung die Teildatei halbiert.

Zum Beispiel kann für das Sortieren einer Datei mit 1000 Datensätzen lediglich die Betrachtung von zehn oder elf Bits jedes Schlüssels erforderlich sein (sogar dann, wenn es sich etwa um Schlüssel mit 32 Bits handelt). Andererseits ist zu bemerken, daß bei gleichen Schlüsseln alle Bits untersucht werden. Digitales Sortieren funktioniert für Dateien, die viele gleiche Schlüssel enthalten, einfach nicht gut. Radix Exchange Sort arbeitet tatsächlich etwas schneller als Quicksort, wenn die zu sortierenden Schlüssel aus wirklich zufälligen Bits bestehen, aber Quicksort kann an weniger zufällige Situationen besser angepaßt werden.

Abbildung 10.3 zeigt den Baum, der den Zerlegungsprozeß für Radix Exchange Sort darstellt; sie kann mit der Abbildung 9.5 verglichen werden. In diesem binären Baum stellen die inneren Knoten die Zerlegungspunkte dar, und die äußeren Knoten sind die Schlüssel in der Datei, die alle in Teildateien der Größe 1 enden. In Kapitel 17 werden wir sehen, wie dieser Baum auf eine direkte Verwandtschaft zwischen Radix Exchange Sort und einem grundlegenden Suchverfahren nahelegt.

Abbildung 10.3
Abbildung 10.3 Baumdiagramm des Zerlegungsprozesses bei Radix Exchange Sort.

Die oben angegebene grundlegende rekursive Implementation läßt sich verbessern, indem man die Rekursion beseitigt und kleine Teildateien anders behandelt, genauso, wie wir es für Quicksort getan haben.


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