1. Einleitung


[ Zurück zum Inhaltsverzeichnis ]

1.1 Grundgedanke


Auch wenn es sich beim Sortieren von Datensätzen um ein sehr "klassisches" Problemgebiet der Informatik handelt, ist es doch immernoch aktuell. Untersuchungen von Experten haben ergeben, dass schätzungsweise 1/4 der heute verbrauchten kommerziellen Rechenleistung für Sortierungen aufgewandt wird, was die Bedürfnisse nach schnellen und leistungsstarken Sortieralgorithmen verdeutlicht. Verwunderlich ist daher auch nicht, dass sich schon die Pioniere der Informatik mit dem Sortierproblem beschäftigt haben und gerade dort schnell Algorithmen entwickelt wurden, die zum Großteil bis zum heutigen Tage aktuell sind und Anwendung in nahezu allen größeren Programmen finden. Entsprechend groß ist die Fülle an Informationen über klassische Sortieralgorithmen; dass damit Bände von Büchern gefüllt werden ist keine Seltenheit. Und trotz der langjährigen Forschungen und wissenschaftlichen Abhandlungen zum Thema werden noch immer viele neue Erkenntnisse in wissenschafltichen Zeitschriften veröffentlicht und sind noch immer viele theoretische sowie praktische Probleme ungelöst.

1.2 Anliegen/Ziele


Ziel des folgenden Artikels soll nicht sein, die elementaren Sortierverfahren näher zu betrachten. Selection-, Insertion-, Bubble- und Shellsort habe ich hingegen in der C-Datei "elem_sort.c" erfasst, wo sie jeder im Selbststudium erforschen kann. Elementare Sortierverfahren haben im Allgemeinen eine Laufzeitkomplexität von O(n2) und sind für uns daher uninteressant (zur näheren Erläuterung der O-Notation bitte den entsprechenden Artikel heranziehen).
Mit dem vorliegenden Artikel wollen ich und Tobias vielmehr ohne Umschweife einen Einblick in die zeitoptimalen Sortierverfahren geben und diese anhand deutlicher Erklärungen, mit Code-Implementationen und Beispielen unterlegt, dem Leser vermitteln. Dass der obligatorische Einstieg weggelassen wurde, fordert allerdings einen kleinen Tribut: so ist der Artikel mehr für angehende Informatiker als für Neueinsteiger gedacht (man sollte zumindest die grundlegenden Algorithmen schon kennen), trotzdem soll er so verständlich wie möglich erscheinen - falls dennoch Fragen offen bleiben, bin ich gern bereit diese per Mail zu beantworten.
Ziel soll es also sein, einige der zeitoptimalen Sortierverfahren zu beschreiben. In den Kapiteln 2 und 3 werden Quicksort und Mergesort behandelt, im 4. Kapitel werde ich mit Tobias auf die Datenstruktur Heap und das darauf aufbauende Heapsort eingehen. Jedes dieser 3 Sortierverfahren stützt sich auf klassische Vergleiche der zu sortierenden Daten, wohingegen die Radixsort's die arithmetischen Eigenschaften der zu sortierenden Schlüssel ausnutzen - die hierzu gehörenden Verfahren werden in Kapitel 5 beschrieben, darunter auch ein Verfahren, welches linear und dazu noch sehr schnell arbeitet.

1.3 Spielregeln


Stillschweigend wird vorausgesetzt, dass bekannt ist, was "zeitoptimal" eigentlich bedeutet. Hierzu vielleicht doch noch ein paar Worte: zeitoptimale Sortierverfahren können eine Datei mit n Schlüsseln in einer Zeitkomplexität von n*log(n) sortieren - wenn es sich um Algorithmen wie Quicksort oder Mergesort handelt, die sich auf Schlüsselvergleiche stützen. Dass diese Komplexität nicht zu verbessern ist, kann leicht durch ein paar Überlegungen gezeigt werden: so kann man das Sortieren von n Schlüsseln als Binärbaum darstellen, dessen Wurzel die ursprüngliche Folge und dessen Blätter alle n! Permutationen dieser Folge sind. Denn jede dieser Permutationen kann als sortierte Folge in Frage kommen, doch nur ein Weg von der Wurzel zur Blattebene ist der gesuchte. Nun ist es aber so, dass n! Blätter eine Mindesthöhe des Baumes von n*log(n) erfordern - daher kann man nicht in weniger als O(n*log(n)) Schritten von einer zufälligen Anordnung zu einer sortierten Folge gelangen. Andere Verfahren wie z.B. das auch besprochene Radixsort greifen auf einzelne Ziffern der Schlüssel zurück, bei ihnen kann man im Optimum von einer linearen Zeitkomplexität O(n) ausgehen, was wohl das Beste ist, worauf man bei einem Sortieralgorithmus hoffen kann.
Zu den Code-Beispielen ist es wichtig zu sagen, dass sie ausschließlich in C implementiert sind. Der Einfachheit halber und damit es noch ein wenig verständlicher wird, werden als Schlüssel dabei immer nur Ganzzahlen (int's) verwendet. Es sollte allerdings kein Problem sein, diese Codes auf andere Schlüsseltypen zu übertragen.

Nun viel Spaß mit dem Artikel und nicht vergessen: immer schön sortiert bleiben =D


[ Zurück zum Inhaltsverzeichnis ]

(c) 2004 by RTC, www.linux-related.de
Dieses Dokument unterliegt der GNU Free Documentation License