Sortierverfahren in C++

von Hubert Schmid vom 2013-10-06

Die meisten Entwickler haben irgendwann schon mal ein Sortierverfahren implementiert. Unabhängig vom verwendeten Algorithmus entstehen beim ersten Anlauf häufig lange und unübersichtliche Funktionen. Erst durch Einführung geeigneter Hilfsfunktionen und funktionale Strukturierung wird der Code schließlich verständlich. Wie das aussehen kann, werde ich in den folgenden Abschnitten anhand von fünf verbreiteten Sortierverfahren zeigen. Das besondere daran ist die funktionale Aufteilung: Statt einer willkürlichen Zerlegung werden wiederverwendbare und generische Funktionen der Standardbibliothek eingesetzt. Damit adressiert diese kleine Übung gleich drei Themen:

Alle fünf Implementierungen haben eine ähnliche Struktur. Es wird jeweils ein Funktionstemplate wie im folgenden Listing verwendet. Die beiden Iteratoren first und last spezifizieren den zu sortierenden Bereich – wie in C++ üblich als halboffenes Intervall. Der Typparameter Compare wird für den Vergleich zweier Elemente verwendet. Dabei kann es sich sowohl um eine Funktion als auch um ein Funktionsobjekt handeln.

template <typename Iterator, typename Compare> void example_sort(Iterator first, Iterator last, Compare&& compare) { // ... }

Die folgenden Listings enthalten nur noch den Rumpf der jeweiligen Funktionstemplates, um auf das Wesentliche zu fokussieren. Die Implementierungen sind bewusst einfach gehalten, und dienen nur zur Veranschaulichung. Für produktiven Code sollte man stattdessen auf die optimierten Implementierungen std::sort und std::stable_sort zurückgreifen.

selection_sort

Selection-Sort gehört zu den einfachsten Sortierverfahren: Man sucht das kleinste Element, stellt es an den Anfang und wiederholt diesen Vorgang für alle weiteren Elemente. Der Algorithmus führt unabhängig vor der ursprünglichen Reihenfolge der Elemente stets Ο(n²) Vergleiche durch. Damit ist er vergleichsweise langsam und für den praktischen Einsatz ungeeignet.

using std::swap; for (auto i = first; i != last; ++i) { // find smallest element from unsorted range auto p = std::min_element(i, last, compare); // place it at the final position swap(*i, *p); }

Die Implementierung ist mit Hilfe der Standardbibliothek sehr einfach. Die Funktion std::min_element liefert einen Iterator auf das kleinste Element, und die Funktion swap vertauscht es mit dem Element an der aktuellen Position. Dabei ist zu beachten, dass Letztere möglicherweise im Namensraum des Elementtyps überladen ist.

insertion_sort

Nur unwesentlich komplexer ist Insertion-Sort: Der Algorithmus läuft der Reihe nach durch alle Elemente und baut stückweise die Sortierung auf, in dem jedes Element an der passenden Stelle eingefügt wird. Im Gegensatz zum Selection-Sort werden nur Ο(n log n) Vergleiche benötigt. Die Laufzeit ist dennoch typischerweise quadratisch. Nur wenn die ursprüngliche Reihenfolge bereits weitgehend sortiert ist, reduziert sich die Laufzeit.

for (auto i = first; i != last; ++i) { // find insertion position for *i (using binary search) auto p = std::upper_bound(first, i, *i, compare); // move *i to p, and shift all elements lying in between std::rotate(p, i, std::next(i)); }

Die Funktion std::upper_bound der Standardbibliothek bestimmt mittels Binärsuche die Einfügeposition für das nächste Element. Die ursprüngliche Reihenfolge gleicher Elemente bleibt dabei erhalten, so dass die Sortierung stabil ist. Die Funktion std::rotate wird für das Einfügen verwendet: Eine Reihe von Elementen wird eine Position nach hinten geschoben, um das einzufügende Element an den Anfang dieser Reihe gesetzt.

merge_sort

Beim Merge-Sort wird der zu sortierende Bereich in zwei gleich große Teilbereiche unterteilt, die rekursiv und unabhängig voneinander sortiert werden. Anschließend werden die beiden sortierten Teilbereiche zu einem sortierten Gesamtergebnis zusammengeführt. Die Laufzeit ist in allen Fällen Ο(n log n), und das Verfahren wird primär für verkettete Listen und stabile Sortierungen verwendet.

auto n = std::distance(first, last); if (n > 1) { // split range into two parts and sort them recursively auto middle = std::next(first, n / 2); merge_sort(first, middle, compare); merge_sort(middle, last, compare); // merge the two sorted parts std::inplace_merge(first, middle, last, compare); }

Die Implementierung ist mit Hilfe der Standardbibliothek denkbar einfach: Zuerst wird die Mitte des zu sortierenden Bereichs bestimmt, und die Funktion rekursiv für die beiden Teile ausgeführt. Die eigentliche Komplexität liegt beim Zusammenführen, doch praktischerweise existiert dafür die Funktion std::inplace_merge. Dadurch beschränkt sich die Implementierung auf wenige Anweisungen.

quick_sort

Wenn keine stabile Sortierung benötigt wird, kommt üblicherweise Quick-Sort zum Einsatz. Die Laufzeit ist in den meisten Fällen besser als bei Merge-Sort – in pathologischen Fällen mit Ο(n²) jedoch gravierend schlechter. Hochwertige Implementierungen überwachen daher den Aufwand während der Sortierung und fallen im Zweifelsfall auf ein anderes Verfahren zurück.

Die folgende Implementierung ist dagegen schlicht gehalten. Das Element in der Bereichsmitte als Pivot-Element verwendet. Dadurch wird die quadratische Laufzeit für den Fall verhindert, in dem die Elemente bereits sortiert sind. Alternativ könnte man das Pivot-Element auch zufällig wählen.

using std::swap; auto n = std::distance(first, last); if (n > 1) { // chose pivot element and move it to the end auto p = std::prev(last); swap(*std::next(first, n / 2), *p); // partition the range based on the pivot element using std::placeholders::_1; auto q = std::partition(first, p, std::bind(compare, _1, std::ref(*p))); // place pivot element at the final position swap(*p, *q); // recursively sort the ranges on both sides of the pivot element quick_sort(first, q, compare); quick_sort(std::next(q), last, compare); }

Im Gegensatz zu Merge-Sort erfordert die Abbruchbedingung der Rekursion bei Quick-Sort mehr Sorgfalt. Das Pivot-Element wird mit dem letzten Element des Bereichs vertauscht. Anschließend wird der Bereich ohne das Pivot-Element basierend auf dem Pivot-Element partitioniert. Mit dem Funktionstemplate std::bind wird ein geeignetes Prädikat konstruiert, und mit dem Funktionstemplate std::partition die Partitionierung durchgeführt. Der Rückgabewert verweist auf das erste Element der zweiten Hälfte, das offensichtlich größer oder gleich dem Pivot-Element ist. Nun werden diese beiden Elemente vertauscht, wodurch das Pivot-Element an seiner endgültigen Position landet, und den gesamten Bereich entsprechend der Vergleichsfunktion partitioniert. Schließlich werden die beiden Partitionen rekursiv sortiert. Dabei wird das Pivot-Element ausgelassen, so dass beide Teilbereiche kleiner werden und die Rekursion in jedem Fall terminiert.

heap_sort

Nicht vernachlässigen sollte man Heap-Sort. Das Verfahren ist insgesamt weniger intuitiv, doch insbesondere für dynamische Sortierung (Stichwort Priority-Queue) essentiell. Es basiert auf binären Heaps, die sich mit einer Laufzeit von Ο(n) aufbauen und von Ο(n log n) in sortierter Reihenfolge wieder abbauen lassen.

auto n = std::distance(first, last); if (n > 1) { // build max-heap in-place (largest element at the top) std::make_heap(first, last, compare); for (auto i = last; i != first; --i) { // remove the largest element from the heap // and place it at the final position std::pop_heap(first, i, compare); } }

Die Standardbibliothek enthält Funktionen für binäre Heaps, die die eigentliche Komplexität kapseln. In obiger Implementierung wird zunächst der unsortierte Bereich mittels std::make_heap in einen binären Heap konvertiert. Alternativ könnte man ihn auch inkrementell durch Aufrufe von std::push_heap aufbauen – was allerdings ein wenig aufwendiger ist. Anschließend wird der Heap in einer Schleife wieder abgebaut, wobei jeweils das größte Element herausgenommen und an seiner endgültigen Position platziert wird. Dieser Abbauch entspricht in der Standardbibliothek den Funktion std::sort_heap.