Wie implementiert man klassische Sortieralgorithmen in modernem C ++?

Algorithmische Bausteine

Beginnen wir mit der Montage der algorithmischen Bausteine aus der Standard Library:

#include <algorithm>    //min_element, iter_swap, 
                        //upper_bound, rotate, 
                        //partition, 
                        //inplace_merge,
                        //make_heap, sort_heap, push_heap, pop_heap,
                        //is_heap, is_sorted
#include <cassert>      //assert 
#include <functional>   //less
#include <iterator>     //distance, begin, end, next

• das iterator-tools wie nicht-Mitglied std::begin() /std::end() sowie mit std::next() sind nur verfügbar, von C++11 und darüber hinaus. Für C++98 muss man schreiben diese selbst. Es gibt Ersatzstoffe, die von Boost.Bereich in boost::begin() /boost::end()und die von Boost.Dienstprogramm in boost::next().
• die std::is_sorted - Algorithmus ist nur verfügbar für C++11 und darüber hinaus. Für C++98, kann dies umgesetzt werden in Bezug auf std::adjacent_find - und eine hand-geschriebene function-Objekt. Boost.Algorithmus bietet auch eine boost::algorithm::is_sorted als Ersatz.
• die std::is_heap - Algorithmus ist nur verfügbar für C++11 und darüber hinaus.

Syntaktische leckereien

C++14 gibt transparente Komparatoren der form std::less<>die wirken polymorph auf Ihre Argumente. Dies verhindert, dass ein iterator-Typ. Dies kann verwendet werden, in Kombination mit C++11 ist "Standard-Funktion template-Argumente zu erstellen eine einzelne überlast für Sortier-algorithmen, die < als Vergleich und diejenigen, die einen benutzerdefinierten Vergleichsfunktion Objekt.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

In C++11, kann man definieren, eine wiederverwendbare template-alias zu extrahieren, die ein iterator - value type fügt die kleine Unordnung zu Sortieren algorithmen Unterschriften:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

In C++98 muss man schreiben zwei überladungen und verwenden Sie den verbose - typename xxx<yyy>::type syntax

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); //general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

• Eine andere syntaktische Feinheit ist, dass C++14 ermöglicht einwickeln Benutzer-definierten Komparatoren durch polymorphe Lambda-Ausdrücke (mit auto Parameter abgeleitet, wie Funktions-template-Argumente).
• C++11 hat nur monomorphe lambdas, verlangen, dass die Verwendung der oben genannten Vorlage alias value_type_t.
• In C++98 ist entweder schreiben muss eine eigenständige Funktion Objekt oder einen Ort, um die ausführliche std::bind1st /std::bind2nd /std::not1 Art der syntax.
• Steigern.Binden verbessert diese mit boost::bind und _1 /_2 Platzhalter-syntax.
• C++11 und darüber hinaus auch std::find_if_notin der Erwägung, dass C++98 muss std::find_if mit einem std::not1 um ein function-Objekt.

C++ - Stil

Gibt es kein allgemein akzeptiertes C++14 Stil noch. Für besser für schlechter, ich verfolge Scott Meyers ' s Entwurf Effektives Modernes C++ und Herb Sutter überarbeitet GotW. Ich verwende die folgenden Stil-Empfehlungen:

• Herb Sutter ""Fast Immer "Auto" und Scott Meyers ' s ""Lieber auto, um den spezifischen Typ-Deklarationen" Empfehlung, für die der Kürze halber ist unübertroffen, obwohl seine Klarheit ist manchmal umstritten.
• Scott Meyers ' s ""Unterscheiden () und {}wenn Objekte zu erstellen" und konsequent wählen verspannt-Initialisierung {} statt der guten alten eingeklammerte Initialisierung () (um side-step alle die-leidige-parse-Probleme, die in generischen code).
• Scott Meyers ' s ""Lieber alias-Deklarationen, Typdefinitionen". Für Vorlagen ist dies sowieso ein muss, und verwenden Sie es überall statt typedef spart Zeit und fügt Konsistenz.
• Ich benutze eine for (auto it = first; it != last; ++it) Muster in einigen Orten, damit die for-Schleife invariante Prüfung für bereits sortierte sub-ranges. In der Produktion code, die Verwendung von while (first != last) und ein ++first irgendwo innerhalb der Schleife könnten etwas besser.

Auswahl Sortieren

Auswahl Sortieren nicht die Anpassung an die Daten in keiner Weise, so dass seine Laufzeit ist immer O(N^2). Aber die Auswahl Art hat die Eigenschaft, die Minimierung der Anzahl von swaps. In Anwendungen, wo die Kosten der swapping-Produkten ist hoch, die Auswahl Sortieren sehr gut kann der Algorithmus der Wahl.

Implementieren Sie unter Verwendung der Standard-Bibliothek, benutz std::min_element zu finden, die Verbleibende Mindest-element, und iter_swap tauschen Sie es in Stelle:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Beachten Sie, dass selection_sort hat die bereits bearbeiteten Bereich [first, it) sortiert, wie seine loop-invariant. Die minimalen Anforderungen sind forward-Iteratorenim Vergleich zu std::sort's random-access-Iteratoren.

Details weggelassen:

• Auswahl Sortieren können optimiert werden, mit einem frühen test if (std::distance(first, last) <= 1) return; (oder für vorwärts - /bidirektionale Iteratoren: if (first == last || std::next(first) == last) return;).
• für bidirektionale Iteratorender obige test kann kombiniert werden mit einer Schleife über dem Intervall [first, std::prev(last))weil das Letzte element wird garantiert der minimale Verbleibende element und nicht um eine swap.

Insertion sort

Obwohl es eine der elementaren Sortier-algorithmen mit O(N^2) worst-case-Zeit, insertion sort ist der Algorithmus der Wahl, wenn die Daten fast sortiert ist (denn es ist adaptive) oder, wenn das problem klein ist (weil es hat einen niedrigen overhead). Aus diesen Gründen, und weil es auch stabilinsertion sort wird Häufig verwendet, um die rekursiven basisfall (wenn das problem klein ist) für höhere overhead-divide-and-conquer-algorithmen zur Sortierung, wie merge-sort oder quick sort.

Umzusetzen insertion_sort mit der Standard-Bibliothek, benutz std::upper_bound um den Ort zu finden, wo das aktuelle element braucht, um zu gehen, und verwenden Sie std::rotate verschieben der restlichen Elemente nach oben in den Eingangsbereich:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Beachten Sie, dass insertion_sort hat die bereits bearbeiteten Bereich [first, it) sortiert, wie seine loop-invariant. Insertion sort funktioniert auch mit vorwärts-Iteratoren.

Details weggelassen:

• insertion sort kann optimiert werden, mit einem frühen test if (std::distance(first, last) <= 1) return; (oder für vorwärts - /bidirektionale Iteratoren: if (first == last || std::next(first) == last) return;) und eine Schleife über dem Intervall [std::next(first), last)weil das erste element ist garantiert an Ort und Stelle sein und erfordert nicht drehen.
• für bidirektionale Iteratorendie binäre Suche zu finden, die Einfügemarke ersetzt werden kann, mit einem reverse lineare Suche unter Verwendung der Standard-Bibliothek std::find_if_not Algorithmus.

Vier Live-Beispiele (C++14C++11C++98 und BoostC++98) für das fragment unten:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();

• Für zufällige Eingaben das gibt O(N^2) Vergleiche, aber dies verbessert sich auf O(N) Vergleiche für fast sortierte Eingaben. Die binäre Suche verwendet immer O(N log N) Vergleiche.
• Für kleine Eingangsbereiche, die bessere Speicher Ort (Caches, prefetching) von einer linearen Suche möglicherweise Dominieren auch eine binäre Suche (sollte man testen, natürlich).

Quick sort

Wenn Sie sorgfältig umgesetzt, quick sort ist robust und hat O(N log N) erwartet die Komplexität, aber mit O(N^2) worst-case-Komplexität, die ausgelöst werden kann, mit adversarially gewählten input-Daten. Wenn eine stabile Sortierung ist nicht erforderlich, quick-sort ist ein hervorragendes, Allgemeines Sortieren.

Selbst für die einfachsten Versionen von quick sort ist ein bisschen mehr kompliziert zu implementieren unter Verwendung der Standard-Bibliothek als die anderen klassischen Sortier-algorithmen. Der Ansatz unten verwendet ein paar iterator utilities zu suchen, die mittlere element der Eingangsbereich [first, last) wie der Drehpunkt, dann verwenden Sie zwei Anrufe zu std::partition (die O(N)) drei-Wege-partition des Eingangsbereichs in Segmente von Elementen, die kleiner als, gleich und größer als das ausgewählte pivot, beziehungsweise. Zum Schluss die beiden äußeren Segmente mit Elementen kleiner als und größer als das pivot sind rekursiv sortiert:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); //assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  //assert(std::is_sorted(middle2, last, cmp));
}

Jedoch, quick sort ist eher schwierig zu bekommen korrekt und effizient ist, als jede der oben genannten Schritte werden sorgfältig geprüft und für die Produktion optimiert-level-code. Insbesondere für O(N log N) Komplexität, die pivot hat zu Folge, dass in einer ausgewogenen Teilung der Eingangsdaten, die nicht garantiert werden kann im Allgemeinen für einen O(1) pivot, aber garantiert werden kann, setzt man die pivot als O(N) median der Eingangsbereich.

Details weggelassen:

• der oben genannten Umsetzung ist besonders anfällig für die speziellen Eingaben, z.B. O(N^2) Komplexität für die "organ pipe" input 1, 2, 3, ..., N/2, ... 3, 2, 1 (denn die Mitte ist immer größer als alle anderen Elemente).
• median-von-3 pivot-Auswahl von "zufällig gewählte Elemente aus dem Eingangsbereich schützt gegen fast sortierte Eingaben, für die die Komplexität würde sich sonst verschlechtern zu O(N^2).
• 3-Wege-Partitionierung (Trennung von Elementen, die kleiner als, gleich und größer als der pivot) wie gezeigt durch die zwei Aufrufe std::partition ist nicht die effizienteste O(N) Algorithmus, um dieses Ergebnis zu erreichen.
• für random-access-Iteratoreneine garantierte O(N log N) Komplexität kann erreicht werden durch median pivot-Auswahl mit std::nth_element(first, middle, last)gefolgt von rekursiven Aufrufe quick_sort(first, middle, cmp) und quick_sort(middle, last, cmp).
• diese Garantie kommt zu einem Preis, aber, weil der Konstante Faktor, der die O(N) Komplexität der std::nth_element teurer sein kann als die O(1) Komplexität eines median-of-3 pivot, gefolgt von einer O(N) Aufruf std::partition (was ist ein cache-freundliche single-vorwärts-Durchlauf über die Daten).

Merge-sort

Wenn mit O(N) zusätzliche Raum nicht von Belang ist, dann merge-sort ist eine ausgezeichnete Wahl: es ist das einzige stabil O(N log N) Sortier-Algorithmus.

Es ist einfach zu implementieren, Verwendung von Standard-algorithmen: verwenden Sie ein paar iterator utilities zu suchen, der Mitte der Eingangsbereich [first, last) und kombinieren Sie zwei rekursiv sortiert Segmente mit einem std::inplace_merge:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); //assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  //assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); //assert(std::is_sorted(first, last, cmp));
}

Merge-sort erfordert bidirektionale Iteratoren, der Engpass wird die std::inplace_merge. Beachten Sie, dass beim Sortieren von verketteten Listen, merge-sort erfordert nur O(log N) extra Raum (für Rekursion). Der letztere Algorithmus wird implementiert, indem std::list<T>::sort in der Standard-Bibliothek.

Heap-sort

Heap-sort ist einfach zu implementieren, führt eine O(N log N) in-place Sortieren, aber ist nicht stabil.

Ersten Schleife O(N) "heapify" - phase, setzt das array in heap um. Die zweite Schleife, die O(N log N) "sortdown" - phase, wiederholt extrahiert den maximalen und stellt die heap-Ordnung. Die Standard-Bibliothek macht dies extrem einfach:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); //assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); //assert(std::is_sorted(first, last, cmp));
}

Falls Sie denken, dass es "Betrug" zu verwenden std::make_heap und std::sort_heap können Sie eine Ebene tiefer und schreiben Sie diese Funktionen selbst in Bezug auf std::push_heap und std::pop_heap bzw:

namespace lib {

//NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   //namespace lib

Die Standard-Bibliothek gibt sowohl push_heap und pop_heap Komplexität O(log N). Beachten Sie jedoch, dass die äußere Schleife über den Bereich [first, last) Ergebnisse in O(N log N) Komplexität für make_heapin der Erwägung, dass std::make_heap hat nur O(N) Komplexität. Für die insgesamt O(N log N) Komplexität der heap_sort ist es egal.

Details weggelassen: O(N) - implementation von make_heap

Testen

Hier sind vier Live-Beispiele (C++14C++11C++98 und BoostC++98) Prüfung alle fünf algorithmen, die auf einer Vielzahl von Eingängen (soll nicht erschöpfend sein oder strengen). Nur beachten Sie die enormen Unterschiede in der LOC: C++11/C++14 müssen rund 130 LOC in C++98 und Boost-190 (+50%) und C++98-mehr als 270 (+100%).

InformationsquelleAutor der Antwort TemplateRex