Robert Sedgewick: Algorithmen

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


10. Digitales Sortieren



Bits

Wenn eine Binärzahl (die die Darstellung eines Schlüssels ist) gegeben ist, besteht die grundlegende Operation, die für digitale Sortierverfahren benötigt wird, im Extrahieren einer zusammenhängenden Menge von Bits aus der Zahl. Nehmen wir an, daß wir Schlüssel zu verarbeiten haben, von denen wir wissen, daß es ganze Zahlen zwischen 0 und 1000 sind. Wir können annehmen, daß sie durch aus zehn Bits bestehenden Binärzahlen dargestellt sind. In der Maschinensprache werden Bits aus Binärzahlen extrahiert, indem bitweise »AND«-Operationen und Stellenverschiebungen angewandt werden. Zum Beispiel werden die beiden führenden Bits einer aus 10 Bits bestehenden Zahl extrahiert, indem eine Stellenverschiebung um acht Bitpositionen nach rechts vorgenommen wird und anschließend ein bitweises »AND« mit der Maske 0000000011 angewandt wird. In Pascal können diese Operationen mit div und mod simuliert werden. Zum Beispiel sind die beiden führenden Bits einer aus zehn Bits bestehenden Zahl x durch (x div 256) mod 4 gegeben. Im allgemeinen kann eine »Stellenverschiebung von x um k Bitpositionen nach rechts« durch die Berechnung von x div 2k simuliert werden, und »alle bis auf die j am weitesten rechts befindlichen Bits von x auf Null setzen« durch die Berechnung von x mod 2j. In unserer Beschreibung der digitalen Sortieralgorithmen werden wir die Existenz einer Funktion (function) bits (x, k, j: integer) : integer voraussetzen, welche diese Operationen in der Weise kombiniert, daß sie die j Bits zurückgibt, die k Bits von rechts in x angeordnet sind, indem sie (x div 2k) mod 2j berechnet. Zum Beispiel wird das am weitesten rechts liegende Bit von x durch den Aufruf bits (x, 0, 1) zurückgegeben. Die Effizienz dieser Funktion kann verbessert werden, indem die Potenzen von 2 vorab berechnet (oder als Konstanten definiert) werden. Es sei bemerkt, daß ein Programm, das nur diese Funktion verwendet, digitales Sortieren bei jeder beliebigen Darstellung der Zahlen ausführen kann. Jedoch können wir auf eine wesentlich erhöhte Effizienz hoffen, wenn die Darstellung binär ist und der Compiler klug genug ist, um zu bemerken, daß die Berechnung tatsächlich mit »SHIFT«- und »AND«-Anweisungen ausgeführt werden kann. Viele Pascal-Implementationen besitzen Spracherweiterungen, die es gestatten, diese Operationen unmittelbar zu spezifizieren.

Mit diesem grundlegenden Werkzeug ausgerüstet, wollen wir zwei Typen von digitalen Sortierverfahren betrachten. Diese unterscheiden sich hinsichtlich der Reihenfolge, in der sie die Bits der Schlüssel untersuchen. Wir setzen voraus, daß die Schlüssel nicht kurz sind, so daß sich die Mühe lohnt, ihre Bits zu extrahieren. Wenn die Schlüssel kurz sind, kann die Distribution Counting-Methode aus Kapitel 8 angewandt werden. Wir erinnern daran, daß diese Methode N Schlüssel, von denen bekannt ist, daß sie ganze Zahlen zwischen 0 und M - 1 sind, in linearer Zeit sortieren kann, wobei sie eine Hilfstabelle der Größe M für die Zählungen und eine weitere der Größe N für das Umordnen der Datensätze verwendet. Daher können Schlüssel mit b Bits leicht in linearer Zeit sortiert werden, wenn wir uns eine Tabelle der Größe 2b leisten können. Digitales Sortieren steht zur Diskussion, wenn die Schlüssel eine so große Länge haben (zum Beispiel b = 32), daß dies nicht möglich ist.

Die erste grundlegende Methode des digitalen Sortierens, die wir betrachten, untersucht die Bits in den Schlüsseln von links nach rechts. Sie beruht auf der Tatsache, daß das Ergebnis von »Vergleichen« zwischen zwei Schlüsseln nur von dem Wert der Bits in der ersten Stelle, in der sie sich unterscheiden (wenn von links nach rechts gelesen wird), abhängt. Folglich erscheinen in der sortierten Datei alle Schlüssel mit führendem Bit 0 vor allen Schlüsseln mit führendem Bit 1; unter den Schlüsseln mit führendem Bit 1 erscheinen alle Schlüssel mit zweitem Bit 0 vor allen Schlüsseln mit zweitem Bit 1 usw. Das digitale Sortierverfahren von links nach rechts, das radix exchange sort (digitales Austausch-Sortierverfahren) genannt wird, sortiert, indem es die Schlüssel systematisch auf diese Weise einteilt.

Die zweite grundlegende Methode, die wir betrachten werden und die straight radix sort (geradliniges digitales Sortieren) genannt wird, untersucht die Bits in den Schlüsseln von rechts nach links. Sie beruht auf einem interessanten Prinzip, durch das das Sortieren von Schlüsseln aus b Bits auf b Sortierungen von Schlüsseln mit 1 Bit zurückgeführt wird. Wir werden sehen, wie sich dies mit dem Distribution Counting kombinieren läßt, so daß ein Sortierverfahren entsteht, das unter recht allgemeinen Voraussetzungen in linearer Zeit abläuft.


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