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 anqsort
, aber das garantiert dir nicht einmal das.
-
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 anqsort
, 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.