Welche Nachteile hat der Algorithmus "Quicksort"?
4 Antworten
Dass die Geschwindigkeit im schlechtesten Fall n² ist. Davon ab ist der Quicksort unstable, was bedeutet, dass bei identischen Eingaben nicht die Reihenfolge der Eingabe beibehalten wird. Das ist vor allem wichtig, wenn man nach mehreren Kriterien nacheinander sortiert.
Eigentlich ist nur die sehr fehleranfällige Implementation ein Nachteil, da sich bei der Rekursion schnell Fehler unbemerkt einschleichen können. Zudem kann man den Algorithmus nicht in Programmiersprachen einsetzen, die keine Rekursion unterstützen.
Wie gut der Quicksort arbeitet hängt vom Einzelfall ab.
LG Knom
- Quicksort wird im Vergleich zu Bubblesort (oder so) langsam für kurze Listen (< 5 oder so)...
- deswegen sollte man nie reines Quicksort verwenden, glaub ich...
- https://stackoverflow.com/questions/46786327/why-bubble-sort-is-faster-than-quick-sort
deswegen sollte man nie reines Quicksort verwenden, glaub ich...
Genau: Man kann eine Fallunterscheidung je nach Eingabelänge vorschalten.
Es gibt auch unterschiedliche Geschwindigkeiten wenn die Liste schon so gut wie sortiert ist bzw. es ist oder umgekehrt. Auch hier ist Quicksort deutlich langsamer als viele andere Verfahren wie z.B. ein Mergesort.
Der Nachteil von Quicksort liegt darin, dass dieses Verfahren im Falle einer schon weitgehend sortierten Folge oder im Falle vieler gleichartiger Schlüsselwerte zu einem Worst-Case-ähnlichen Verhalten führt.