Was sind die Vorteile und Nachteile von Quicksort gegenüber Bubblesort?
3 Antworten
Hallo Robo267!
Bubblesort hat folgende Vor- und Nachteile:
✓ Einfach zu programmieren
☓ Langsam
☓ Nicht leistungsfähig
Quicksort hat folgende Vor- und Nachteile:
✓ Schnell bei großen Feldern
✓ Effizient
✓ Einfach zu implementieren
☓ Sehr störanfällig
☓ Langsam bei kleinen Feldern
☓ Großer Speicherbedarf
Ich hoffe ich konnte dir helfen. :-)
Alles Liebe
Sarah
Was bedeutet denn "störanfällig"? Quicksort sortiert in-place. So gibt es da einen "großen Speicherbedarf"?
- BubbleSort: stabil, best case: O(n), average: O(n^2), worst: O(n^2)
- QuickSort: instabil, best case: O(n*log(n)), average: O(n*log(n)), worst: O(n^2)
"Stabil" heißt dabei, dass die Elemente mit gleichem Wert die Reihenfolge beibehalten.
Quicksort ist weniger intuitiv, nicht stabil und hat eien höhere Speicherkomplexität.
Quicksort ist im Worstcase ebenso langsam wie Bubblesort.
Bubblesort ist stabil und sehr einfach, dafür eben auch langsam.
So, jetzt als Ergänzung, nachdem ich nochmal kurz nachgedacht habe, der Speicherbedarf liegt bei O(log n) bis O(n), mit log hatte ich etwas zu schnell geschossen.
Bubblesort braucht hier halt nur O(1).