Navigation

Sortieralgorithmen in C++

1. Sortieralgorithmen in C++

Sortieralgorithmen gibt es wie Sand am Meer: von hoffentlich nicht ganz ernst gemeinten Verfahren wie etwa Bogosort, über populäre trivial Algorithmen wie Bubblesort bis hin zu recht performanten Algorithmen wie etwa Quicksort, Heapsort oder Introsort. Im Folgenden werden einige Sortieralgorithmen und deren Implementierung in C++ vorgestellt. Die hier vorgestellten Routinen sind auch downloadbar.

1.1. Übersicht über die Sortieralgorithmen

Die folgende Tabelle enthält eine Liste der vorgestellten Sortierverfahren. Sollte die Bedeutung der einen oder anderen Spalte nicht klar sein, bitte im nächsten Abschnitt einfach mal nachschauen.

AlgorithmusAllgemein?Geschwindkeit (günstigster, durchsschn., schlechtester Fall)PlatzbedarfStabil?Iterator
Bogosort Ja O(n), O(nn!), unendlich in situ Nein RandomAccess
Selectionsort Ja O(n2), O(n2), O(n2) in situ Ja Forward
Insertionsort Ja O(n), O(n2), O(n2) in situ Ja Bidirectional
Bubblesort Ja O(n), O(n2), O(n2) in situ Ja Bidirectional
Quicksort Ja O(n log n), O(n log n), O(n2) in situ Nein Bidirectional
Mergesort Ja O(n log n), O(n log n), O(n log n) O(n) Ja RandomAccess
Heapsort Ja O(n), O(n log n), O(n log n) in situ Nein RandomAccess
Introsort Ja O(n log n), O(n log n), O(n log n) in situ Nein RandomAccess

1.2. Eigenschaften von Sortieralgorithmen

Sortieralgorithmen verfolgen generell das Ziel, eine (unsortierte) Folge A von n Elementen gemäß eines Sortierkriteriums zu ordnen. Insbesondere, wenn die Anzahl der zu sortierenden Elemente (also n) recht groß ist, ist die Geschwindigkeit des Sortierverfahrens sicherlich von großer Bedeutung. Aber dies ist nicht immer das einzige Kriterium: Auch ggf. für den Sortiervorgang zusätzlich benötigter Speicher kann eine Bedeutung haben, ebenso die Frage, ob gleich große Elemente in der gleichen Reihenfolge in der sortierten Elementfolge auftreten, wie in der unsortierten. Im Folgendem sind deshalb also einige Merkmale zusammengefaßt, welche für jeden Sortieralgorithmus neben der Implementierung auch untersucht werden. Eine Zusammenfassung dieser Kenndaten findet sich auch in der Übersicht weiter oben:

1.2.1. Geschwindigkeit

Geschwindigkeiten sind im allg. nicht direkt vergleichbar. In der Informatik hat man daher die sog. Landau-Notation (auch O-Notation genannt) eingeführt, um das Laufzeitverhalten von Algorithmen zu vergleichen. Ohne jetzt auf die theoretischen Details einzugehen (welche im Link viel besser erklärt sind), genügt es an dieser Stelle zu wissen, daß die Landau-Notation angibt, wie sich die Laufzeit eines Algorithmus asymptotisch verhält. Bei Sortieralgorithmen ist leicht einsehbar, daß die Zeit, die der Algorithmus zum Sortieren benötigt von n, also der Anzahl der zu sortierenden Elemente abhängig ist. Hat ein Sortieralgorithmus die Laufzeit von O(n), so heißt dies, daß die Laufzeit des Sortieralgorithmus linear mit der Anzahl der zu sortierenden Elemente wächst. Eine Laufzeit von O(1) würde bedeuten, daß der Algorithmus unabhängig von der Anzahl der Elemente immer gleich schnell ist, wogegen O(n2) bedeutet, daß der Aufwand mit Anzahl der Elemente quadratisch ansteigt. Typische Laufzeiten für gute Sortieralgorithmen liegen bei O(n log n). Man kann beweisen, daß allgemeine Sortieralgorithmen nicht schneller als O(n log n)-O(n) sortieren können (nicht unversell einsetzbaren Algorithmen können aber durchaus schneller sein.

Im folgenden werde ich meist die Laufzeiten der jeweiligen Algorithmen in günstigsten, schlechtesten, und durchschnittlichen Fall angeben. Da leider insbesondere die Herleitung der duchschnittlichen Laufzeit mitunter kompliziert und länglich ist, werde ich manchmal auf die Herleitung der Laufzeit verzichten.[/p]

Generell darf man die in der O-Notation gegebenen Laufzeit jedoch nicht zu sehr auf die Goldwaage legen: so sind Sortieralgorithmen, welche gemäß der O-Notation gleich schnell sind, nicht wirklich gleich schnell: Die O_Notation ist eine stark vergröbernde Sicht, welche z.B. nicht ausdrücken kann, daß ein Algorithmus stets doppelt so schnell ist wie ein anderer. Derartige Analysen sind extrem aufwendig und werden hier allenfalls am Ende experimentell mit Hilfe von Benchmarks gemacht.

TODO: Tabellen einfügen um Laufzeiten mal plastisch zu Vergleichen

1.2.2. Universalität

Sicherlich macht es einen Unterschied, ob ein Sortieralgorithmus bestimmte Annahmen bzgl. der zu sortierenden Elemente machen kann. Ist beispielsweise bekannt, daß die Elemente Zahlen im Bereich zwischen 1 und 100 sind, lassen sich leicht Algorithmen finden, welche eine Laufzeit von O(n) haben. Kann man keine solche Annahmen machen, so ist der Sortieralgorithmus ein allgemeiner Sortieralgorithmus.

1.2.3. In situ und extern

Ein weiteres Unterscheidungsmerkmal ist, ob ein Sortieralgorithmus zusätzlich Speicher benötigt, etwa um eine Kopie der originalen Element Folge oder Teilen von ihr zu speichern. Bei großen Elementfolgen kann dies ein schwerwiegendes Problem sein. Unter einem externen Sortieralgorithmus versteht man ein Verfahren, welches zusätzliche Speicher benötigt. Dagegen ist ein Sortieralgorithmus in situ, wenn er keine zusätlichen Speicherbedarf hat.

1.2.4. Stabilität

Weiterhin ist eine interessante Eigenschaft, wie stark Elemente, welche nach den gleichen Sortierschlüssel besitzen, durch den Algorithmus durcheinander gewürfelt werden. Nehmen wir beispielsweise an, daß wir eine Liste von Personen gemäß deren Nachnamen sortieren wollen, wobei die Liste aber bereits nach deren Vornamen sortiert ist, so ist die Frage durchaus interessant, ob Personen mit gleichen Nachnamen nach Anwendung des Sortieralgorithmus nach wie vor noch nach dem Nachnamen sortiert sind, oder ob die vorherige Vorsortierung komplett ignoriert wird. Ein Sortieralgorithmus, welcher die Vorsortierung beachtet (d.h. Elemente mit gleichem Siortierschlüssel in der gleichen Reihenfolge in die sortierte Folge einfügt, wie er sie in der unsortierten Folge vorfand), wird als stabil bezeichnet

1.3. Ein paar Worte zu den Implementierungen

Bevor wir mit dem ersten Sortieralgorithmus loslegen, möchte ich noch kurz ein paar Worte zu den C++ Umsetzungen der Algorithmen loswerden: Alle Implementierung sind Funktionstemplates, welche Iteratoren und Functoren nutzen. Ich gehe davon aus, daß das Templatekonzept von C++ bekannt ist, ich werde es jedenfalls nicht weiter erläutern. Jedoch werde ich kurz erklären, wie hier Iteratoren benutzt werden und die Eigenschaften von Iteratoren hinsichtlich der Sortieralgorithmen kurz anreißen. Gleiches gilt für die Functoren. Wer bzgl. C++ das Anfängerstadium bereits verlassen hat, kann den folgenden Abschnitt daher getrost überspringen.

TODO: ForwardIterator, BidirectionalIterator, RandomAccessIterator erklären

TODO: Functoren erklären