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 ]