Quicksort vs mergesort laufzeit?

3 Antworten

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.

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.

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.

1

https://youtu.be/kPRA0W1kECg

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

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

Was möchtest Du wissen?