QuickSort in C++17 wie in Python?



  • In Python kann man ja QuickSort ganz kurz schreiben:

    def quicksort(list):
        if len(list) <= 1:
            return list
        else:
            pivot = list[0]
            return quicksort([a for a in list if a < pivot]) + [pivot] + quicksort([a for a in list if a > pivot])
    

    Geht das ähnlich auch in C++17?



  • c+++++++ schrieb:

    In Python kann man ja QuickSort ganz kurz schreiben:

    def quicksort(list):
        if len(list) <= 1:
            return list
        else:
            pivot = list[0]
            return quicksort([a for a in list if a < pivot]) + [pivot] + quicksort([a for a in list if a > pivot])
    

    Geht das ähnlich auch in C++17?

    lölchen.
    Im Prinzip geht das auch schon lange, satt + halt eine Funktion, die Listen aneinanderhängt.
    Aber es ist in C++ ein Oberverbrechen, Quicksort zu vergewaltigen und so langsam zu machen wie in diesem Beispiel.
    Meiste nicht auch, daß für pythonischen Listen sich Varianten von Mergesort eher anböten?



  • Wie würdest du MergeSort implementieren?



  • c+++++++ schrieb:

    Wie würdest du MergeSort implementieren?

    rekursiv.
    len, [:], append, pop(0), [0]

    und dann würde ich auf https://wiki.python.org/moin/TimeComplexity schauen und mir QuickSort wünschen, aber ohne Kopieren von Listen, sondern mit Indizes direkt in der Hauptliste arbeiten.

    Hab fäschlicherweise gedacht, die Listen seien nicht bloß plumpe Arrays, weil [:] und + und so Sachen doch arg oft in Python zu sehen sind.



  • Ist nicht der STL algorithmus sort soiweso quicksort?



  • Sewing schrieb:

    Ist nicht der STL algorithmus sort soiweso quicksort?

    Nicht zwangsläufig. std::sort macht lediglich Vorgaben zur Komplexität. Vielleicht denkst du an qsort , aber das garantiert dir nicht einmal das.


  • Mod

    Kopiergerät schrieb:

    Sewing schrieb:

    Ist nicht der STL algorithmus sort soiweso quicksort?

    Nicht zwangsläufig. std::sort macht lediglich Vorgaben zur Komplexität. Vielleicht denkst du an qsort , aber das garantiert dir nicht einmal das.

    Da ein reines Quicksort die vorgemachten Anforderungen nicht erfüllt, wird es in C++-Implementierungen auch nie Quicksort sein. Üblicherweise sind es hybride Verfahren, wie z.B. Introsort.



  • c+++++++ schrieb:

    In Python kann man ja QuickSort ganz kurz schreiben:

    def quicksort(list):
        if len(list) <= 1:
            return list
        else:
            pivot = list[0]
            return quicksort([a for a in list if a < pivot]) + [pivot] + quicksort([a for a in list if a > pivot])
    

    Geht das ähnlich auch in C++17?

    Diese Implementierung hat ein paar Probleme: (1) Wenn da die Werte mehrfach in der Python-Liste auftauchen und ein solcher Wert als Pivot-Wert gewählt wird, fliegen die Duplikate raus und Deine Liste wird kürzer. (2) Diese Implementierung ist nicht besonders performant. Quicksort kann man "in-place" ausführen und muss nicht über solche List-Comprehensions und Konkatenationen ständig neuen Speicher anfordern.

    Wenn man sich aber ein paar Hilfsfunktionen in C++ drumherum baut, könnte Deine Quicksort-Implementierung in C++17 so aussehen:

    template<class T>
    auto quicksort(vector<T> const& list) -> vector<T>
    {
        if (v.size() <= 1) {
            return list;
        } else {
            auto& pivot = list[0];
            return quicksort(filtered(list, [&](auto& x){ return x < pivot; })) +
                   vector<T> { pivot } +
                   quicksort(filtered(list, [&](auto& x){ return x > pivot; }));
        }
    }
    

    filtered ist hier jetzt Funktions-Template, das nicht standard ist und selbst bereitgestellt werden müsste. Das gleiche gilt für diesen "+" Operator zum Aneinanderhängen der Vektoren.

    Aber wie gesagt, hier wird unnötiv viel kopiert und unnötig viele kleine temporäre Vektoren angelegt. Es ist totaler Mist im Vergleich zu einem Quicksort, der "in-place" arbeitet. 🙂


Log in to reply