Die Art der Sortierung wird in der std::sort()?

Kann jemand bitte sagen Sie mir, welche Art von Sortier-Technik (bubble, insertion, selection, quick -, merge -, zählen,...) implementiert ist, in der std::sort() definierte Funktion in der <algorithm> header-Datei?

Nicht deine Frage, aber es sagt hier: cplusplus.com/reference/algorithm/sort, nlogn durchschnittlich und n^2 worst case (das gleiche gilt für quicksort).
MSVC Hilfe auch fest, dass "Die Durchschnittliche von einer Art von Komplexität ist O(N log N), wobei N = _Last – _First."
BTW-Die Antwort für die c-standard-library-Funktion sort() ist die gleiche: etwas, das läuft bei O(N log N). Manchmal manpage wird Ihnen sagen, was das system tatsächlich verwendet wird.

InformationsquelleAutor Vaibhav | 2009-12-03

  1. 28

    Meisten Implementierungen von std::sort verwenden quicksort, (oder in der Regel ein hybrid-Algorithmus wie introsort, die kombiniert quicksort, heapsort und insertion sort).

    Das einzige, was der standard verlangt, dass std::sort irgendwie Sortieren Sie die Daten nach der angegebenen Bestellung mit einer Komplexität von etwa O(N log(N)); es ist nicht garantiert stabil zu sein. Technisch, introsort besser begegnet der Komplexität Anforderung als quicksort, weil quicksort hat quadratische worst-case-Zeit.

    Tun Sie etwas quicksorting Umsetzung von std::sort? Die, die ich gesehen habe, verwenden alle die introsort von der original-STL. Pro C++11, die O(n lg n) Voraussetzung ist, nicht mehr "Ungefähre".
    Auch (zumindest in visual studio) scheint es sich um eine Optimierung durchzuführen, zählen Sie die Sortierung für die kleinen reichten die zahlen. Ich habe nicht die Umsetzung, aber ich weiß, die Sortierung ist linear für mehr als eine million zahlen im Bereich von etwa 1 million.
    Ich habe nie gesehen, eine Umsetzung, die nicht mit introsort. Sie sollten entweder ein back-up "die Meisten Implementierungen..." behaupten oder zu ändern, Ihre Antwort.
    Ich gab eine ähnliche Antwort, unten mit mehr details auf introsort. Außerdem denke ich, dass introsort war immer die "standard-STL-Implementierung" von std::sort von Anfang an (und nicht von quicksort).

    InformationsquelleAutor Charles Salvia

  2. 10

    C++ - Standard ISO/IEC 14882:2003

    25.3.1.1 Art

    template<class RandomAccessIterator>
   void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
   void sort(RandomAccessIterator first, RandomAccessIterator last,
          Compare comp);

    1 Effekte: Sortiert die Elemente in der
    Bereich [first, last).

    2 Komplexität:
    Etwa N log N (N == Letzte
    - erste) Vergleich über dem Durchschnitt.

    Gibt es keine Informationen über Methode, aber Komplexität ist immer N log N.

    Dein text und das Zitat passen nicht zusammen. N log N ist im Durchschnitt, aber es sagt nichts über schlimmsten Fall.

    InformationsquelleAutor Alexey Malistov

  3. 7

    Es gibt drei algorithmen, die verwendet werden in MSVC2013 STL, bezogen auf den source-code von std::sort.

    Ist es sehr wahrscheinlich, dass Sie QuickSort oder eine variation über QuickSort genannt IntroSort.

    Wenn die Rekursion geht zu tief, die HeapSort hier verwendet werden.

    Sonst InsertSort verwendet werden.

    InformationsquelleAutor zangw

  4. 4

    Wahrscheinlich alle Implementierungen von std::sort verwenden introsort (aka Introspektion Art), ein hybrid-Algorithmus, kombiniert quicksort und heapsort. Eigentlich introsort wurde vor allem erfunden im Jahre 1997 für die Zwecke einer performanten Art Implementierung in C++ STL.

    Das einzige, was der standard verlangt, dass std::sort irgendwie Sortieren Sie die Daten nach der angegebenen Bestellung mit einer Komplexität von O(N log(N)); es ist nicht garantiert stabil zu sein (es gibt eine separate std::stable_sort algorithmen zur Verfügung, sollte dies notwendig sein).

    Technisch, introsort besser begegnet der Komplexität Anforderung als quicksort: Dies ist, weil heapsort garantiert O(N log(N)) Komplexität im schlimmsten Fall, in der Erwägung, dass quicksort hat quadratische worst-case-Zeit.

    Aber heapsort ist 'langsamer' als quicksort im durchschnittlichen Fall, in dem Sinn, dass heapsort führt C*N log(N) in der Erwägung, dass quicksort hat D*N log(n) Leistung, mit D deutlich kleiner als C (die zahlen C und D sind Konstanten). In anderen Worten, die pro-Vergleich-overhead von heapsort ist höher als die von quicksort.

    Erhalten das beste aus beiden Welten, introsort beginnt mit quicksort ein rekursiver Algorithmus—, aber wenn die Rekursionstiefe zu hoch wird (was bedeutet, es wird in einem degeneriert worst-case-Verhalten), schaltet heapsort.

    Siehe auch der Wikipedia-Eintrag für introsort oder die original Papier von David Musser, wer erfand introsort besonders für STL.

    Ich basiert meine Antwort auf, die der stackoverflow.com/users/168288/charles-salvia. Ich zuerst versuchen, zu aktualisieren/ändern/Bearbeiten seine Antwort, aber Moderatoren vorgeschlagen, um eine separate Antwort.

    InformationsquelleAutor King Thrushbeard

  5. 0

    Meinst du mit std::sort? Wenn Sie so umgesetzt werden können wie Sie wollen. Seine wahrscheinlich Schnell Sortieren, sondern könnte radix oder etwas anderes. So lange, wie es produziert man eine sortierte Liste, die in mindestens O(n log n) die Umsetzung ist in Ordnung, soweit ich weiß.

    Es ist auch eine komplexe Anforderung, dass der Algorithmus O(n log n). Das ist nicht viel von einer Beschränkung, da fast alle gängigen Sorten erfüllen diese requerment. Ist verhindert die Nutzung von Bogo sort (en.wikipedia.org/wiki/Bogo_sort).
    Danke, Post editiert 🙂
    Ich nehme an, radix sort nicht erlaubt, (obwohl es könnte effizient sein, für bestimmte Daten-Typen), da Sie nicht haben logarithmische Komplexität, da es nicht die Basis auf Vergleiche.
    Nein, eine O(1) Implementierung wäre in Ordnung. Die Anforderungen sind eine Obere Schranke für die Komplexität. Sie sind in der Regel festgelegt, um die effizienteste wissen, die Implementierung, aber nicht ausschließen, dass einige neue Datenstruktur oder ein Algorithmus, der effizienter ist.
    std::sort ist-Vergleich basiert, die inhärent verhindert, dass Implementierungen schneller als O(n log n).

    InformationsquelleAutor Goz

  6. 0

    Nur einige empirische Ergebnisse:

    Übersetzte ich ein python-script mit numpy 1.9.2 Art zu C++ mit std::sort (VS2008 toolchain).

    Bekomme ich nur die gleichen Ergebnisse in der python-und C++ - Seiten werden bei der Verwendung von numpy.Sortieren argument Art='mergesort'. Ich bekomme verschiedene relative Reihenfolge der Elemente mit gleichem Schlüssel beim freundlichen='quicksort' oder Art='heapsort'. Ich denke also, dass zumindest für die version der STL, die kommt mit VS2008 std::sort mergesort verwendet.

    InformationsquelleAutor martinako

Schreibe einen Kommentar