Geschwindigkeit von Quicksortalgo
-
Hallo Leute,
Ich hab mir gerad aus dem Net folgende Formel herausgesucht zur Geschwindigkeit
von Quicksortn * lg(n) = Anzahl der Vergleiche denk ich mir
Kennt jemand eine Seite oder die Formel für die Anzahl der Tausche im günstigsten und im ungünstigsten Fall bzw. ist die Formel für die Anzahl der Vergleiche die selbe für günstigsten/ungünstigsten FAll.
Im günstigsten Fall vermute ich 0 Tausche.
-
Im günstigsten Fall vermute ich 0 Tausche.
eine sortierte menge zu sortieren wär ja auch sinnlos...
//edit hier im forum gibts auch schon jede menge zu dem thema, sollte nicht sos chwer sein das zu finden
-
Na so logisch ist das nicht, weil beim SelectionSort werden die Elemente
(Auch bei einer sortierten Menge) n mal getausch. Wobei n die Anzahl der Elemente wiederspiegelt.
-
BasicMan01 schrieb:
Im günstigsten Fall vermute ich 0 Tausche.
Aber n Vergleiche. Also T_best = O(n). Im Schnitt sind es T_avg = O(n*log n), hast du ja auch schon gesagt. Im schlimmsten Fall kann es zu T_worst = O(n^2) dauern.
-
Vorsicht, der Standard-Quicksort-Algo hat auch im Bestcase nur eine Laufzeit von n*logn
-
@otze: Eine sortiertes Array ist gerade der worstcase für QS. Für bereits vorsortierte Arrays ist natürliches Mergesort nicht schlecht.
-
der worst case entsteht, wenn man stets das kleinste oder grösste element als pivotelement erwischt - das hat mit der vorliegenden sortierung zunächst nichts zu tun. der best case ist, wenn alle elemente gleich sind, und dann hat man tatsächlich eine laufzeit von n.
-
pasti schrieb:
@otze: Eine sortiertes Array ist gerade der worstcase für QS. Für bereits vorsortierte Arrays ist natürliches Mergesort nicht schlecht.
Aber nicht wenn du den Median der 3 nimmst. Dann ist ein sortiertes Array nähmlich optimal da der Median der 3 (ersters, letztes und das Element in der Mitte) nähmlich auch das Median des ganzen Arrays ist.
-
@camper: Viele QS Implementierungen benutzen immer das letzte Element als Pivot
@Ben04: Du hast recht, aber es gibt immer noch recht viele Permutationen ( z.b. gerade Zahlen vorne im Array einsortiert, ungerade hinten) die auch mit MoT O(n²) Laufzeit benötigen.
-
pasti schrieb:
@Ben04: Du hast recht, aber es gibt immer noch recht viele Permutationen ( z.b. gerade Zahlen vorne im Array einsortiert, ungerade hinten) die auch mit MoT O(n²) Laufzeit benötigen.
QS ist nun einmal ein Algo der hofft, dass die Daten vorteilhaft verteilt sind um schnell zu sein. Man muss ihn halt immer auf eine spezielle Situation einstellen. Bei deinem Beispiel würde ich den Median von den Elementen auf Position 1/4 und 3/4 vom ganzen Array. Meistens sind die Daten ja nicht zufällig verteilt und von daher kann der Programmierer nachhelfen. Sollten die Daten allerdings wirklich zufällig verteilt sein würde ich zu Heapsort raten.
-
Ben04 schrieb:
Sollten die Daten allerdings wirklich zufällig verteilt sein würde ich zu Heapsort raten.
Wie das?
Gerade im Falle von zufälligen Daten geht doch die Argumentation mit der erwarteten Laufzeit von O(n*log n) voll durch.
Man kann auch einfach ein Pivot zufällig ziehen. Man kann zeigen, daß die Laufzeit dann ebenfalls Erwartungswert in O(n*log n) hat. Das ist wohlgemerkt was anderes als den Schnitt über alle Eingaben anzuschaun... der stimmt auch, wenn man immer das selbe Element nimmt. Zieht man zufällig, so hat man für jede Eingabe mit hoher Wahrscheinlichkeit eine gute Laufzeit.
-
in einem meiner schlauen bücher stand mal, dass bottom-up-heapsort besser ist als QS wenn n>=400 und besser als CleverQS falls n>=16000 ist.
Zudem hat Heapsort ein worst-case laufzeitverhalten von O(n log n) und QS O(n^2) AFAIK.rapso->greets();
-
Ich bezog mich hauptsächlich auf die Bemerkung: bei zufällig verteilten Daten. Denn genau da liefert mir der Quicksort ja ne gute erwartete Laufzeit.
Der worst-case ist halt recht selten. Außerdem läßt sich der QS so prima optimieren.
Im konkreten Fall kommt man wahrscheinlich nicht um eine Messung herum.
