Quicksort vs mergesort laufzeit?

Quicksort : worst case (n^2) , average case/best case (n log n) Mergesort : immer n log n

Ich versteh nicht wieso man sagt dass quicksort besser sein soll, wenn mergesort immer mindestens genau so schnell ist wie der best case von quicksort. Hat da jemand eine ahnung wann es sinn macht quicksort zu benutzen ?

Answer 1

[User16495]

Wer hat das jemals gesagt? Der Vorteil von Quicksort ist lediglich, dass er super einfach zu implementieren ist. Du hast also vollkommen recht und alles richtig verstanden ;-)

Sollte was anderes in Deinen Unterlagen stehen, frag nochmal nach, das ist höchstwahrscheinlich ein Fehler.

Comments

[HansImGlueck178]

Der Vorteil ist auch, dass Quicksort nur konstanten Speicher braucht, also in-place ist. Mergesort braucht O(n), also linear viel Speicher. Und Quicksort ist endrekursiv, was gewaltige Laufzeitverbesserungen mit sich bringt.

Answer 2

[HansImGlueck178]

Mergesort benötigt O(n) Speicher, der Speicherbedarf von Quicksort ist konstant (in-place). Allein das allozieren und deallozieren dieses Speichers ist eine ziemliche Einbuße bei der Laufzeitperformanz.

Dazu ist Quicksort endrekursiv, was viele Optimierungsmöglichkeiten mit sich bringt.

Answer 3

[Knomle]

https://youtu.be/kPRA0W1kECg

0:40 ist der Quicksort
1:07 ist der Mergesort

Woher ich das weiß: Studium / Ausbildung – Softwareentwickler mit 10 Jahren Berufserfahrung 💾