Quicksort am effizientesten?

Warum ist Quicksort im Gegensatz zu Bubblesort und Minsort am effizientesten?

Answer 1

[jort93]

Ist es nicht unbedingt, in einer (teilweise) vorsortierten liste ist die laufzeit von bubble sort(oder auch insertion sort) manchmal kürzer als bei quicksort. Und listen sind ziemlich häufig schon vorsortiert, denn du bekommst ja selten völlig zufällige daten.

Dieses divide and conquer verfahren ist halt einfach schneller bei zufälligen daten wenn das pivotelement irgendwo in der mitte ist.

Du kannst dir ja die algorithmen anschauen, weder bubblesort noch quicksort sind besonders komplex.

Answer 2

[KarlRanseierIII]

Verschiedene Sortierverfahren haben verschiedene Stärken und Schwächen.

Unter der Voraussetzung, daß:

1.) Die Daten unsortiert sind

2.) Diese nur durch Vergleich sortiert werden können (Wir können keien anderen Eigenschaften der Objekte nutzen)

3.) Die Daten komplett in den Speicher passen

Ist Quicksort der Champion, weil er die niedrigste Komplexität aufweist.

D.h. je nach Anwendungsfall gibt es also auch bessere Algorithmen, die den Job schneller und/oder mit weniger Speicherkomplexität schaffen.

Answer 3

[Minihawk]

Quicksort hat das beste Laufzeitverhalten, was die Kurve angeht, Anzahl sortierender Felder zu Sortierzeit.