Robert Sedgewick: Algorithmen

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


10. Digitales Sortieren



Die »Schlüssel«, die benutzt werden, um die Reihenfolge der Datensätze für Dateien festzulegen, können für viele Sortieranwendungen sehr kompliziert sein. (Man betrachte zum Beispiel die Ordnungsfunktion, die in einem Telefonbuch oder im Katalog einer Bibliothek verwendet wird.) Aus diesem Grunde ist es sinnvoll, Sortiermethoden mit Hilfe der Grundoperationen des »Vergleichens« zweier Schlüssel und des »Austauschens« zweier Datensätze zu definieren. Die meisten Verfahren, die wir untersucht haben, können mittels dieser beiden grundlegenden Operationen beschrieben werden. Für viele Anwendungen ist es jedoch möglich, aus der Tatsache Nutzen zu ziehen, daß man sich die Schlüssel als Zahlen aus einem bestimmten beschränkten Zahlenbereich vorstellen kann. Sortiermethoden, bei denen die digitalen Eigenschaften dieser Zahlen ausgenutzt werden, heißen digitale Sortierverfahren (radix sorts). Diese Verfahren vergleichen nicht einfach Schlüssel; sie verarbeiten und vergleichen Teile von Schlüsseln.

Digitale Sortieralgorithmen behandeln die Schlüssel als Zahlen in einem Zahlensystem zur Basis M (für verschiedene M) und bearbeiten die einzelnen Ziffern der Zahlen. Betrachten wir zum Beispiel einen Angestellten, der einen Stoß Karten sortieren muß, auf denen dreistellige Zahlen stehen. Eine sinnvolle Vorgehensweise besteht für ihn darin, zehn Stöße anzulegen, nämlich einen für die Zahlen, die kleiner als 100 sind, einen für die Zahlen von 100 bis 199 usw., die Karten auf diese Stöße zu verteilen und sich dann die Stöße einzeln vorzunehmen, unter Anwendung derselben Methode auf die folgende Ziffer oder unter Anwendung eines einfacheren Verfahrens, wenn nur wenige Karten vorhanden sind. Dies ist ein einfaches Beispiel für ein digitales Sortieren mit M = 10. Im vorliegenden Kapitel betrachten wir diese und einige weitere Methoden ausführlich. Natürlich ist es bei den meisten Computern zweckmäßiger, mit M = 2 (oder einer Potenz von 2) als mit M = 10 zu arbeiten.

Alles, was im Inneren eines Digitalrechners dargestellt wird, kann als Binärzahl behandelt werden; daher können viele Sortieranwendungen so umgestaltet werden, daß die Benutzung von digitalen Sortiermethoden möglich wird, die mit aus Binärzahlen bestehenden Schlüsseln operieren. Leider machen Pascal und viele andere Sprachen es absichtlich schwer, Programme zu schreiben, die von der Binärdarstellung von Zahlen abhängen. (Der Grund besteht darin, daß Pascal als eine Sprache konzipiert ist, die Programme in einer vom Computer unabhängigen Weise formuliert, und verschiedene Computer für die gleichen Zahlen unterschiedliche Darstellungen benutzen können.) Diese Philosophie macht viele Arten von »Bit-Manipulations«-Techniken unnötig, besonders in Situationen, die sich zweifellos mit Hilfe von grundlegenden Pascal-Elementen wie Datensätzen und Mengen (sets) besser handhaben lassen; digitales Sortieren scheint jedoch eine Schwachstelle in dieser progressiven Philosophie zu sein. Glücklicherweise ist es nicht allzu schwierig, arithmetische Operationen zu benutzen, um die benötigten Operationen zu simulieren, und damit sind wir hier in der Lage, (uneffiziente) Pascal-Programme zur Beschreibung der Algorithmen anzugeben, die leicht in effiziente Programme in Programmiersprachen, die Bitoperationen mit Binärzahlen unterstützen, übertragen werden können.


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