[DSAL] Quicksort mit den Median-der-Mediane.

[LonliLokli]

Was ist Laufzeit vom Quicksort, wenn für das Pivot-Element mit dem Median der Mediane gewählt wird (O(n)) gewält wird und die Folge aus n - gleich grossen Elementen besteht?

[Martin]

Ich hab mal einfach geraten, dass [DaStru] der richtige Tag ist. Falls ich da falsch liege, bitte korrigieren...

[LonliLokli]

Ich hab mal einfach geraten, dass [DaStru] der richtige Tag ist. Falls ich da falsch liege, bitte korrigieren...

Richtig... aber ich erinnere mich daran, diesen Tag gemacht zu haben.

Vielleicht erleutere ich bisschen mein Problem:
man weiss, dass mit ungünstigen Pivot-Element dieser Sort. Alg laufzeit von hat. Man versucht mit dem Medianen Alg. dieses falsche Element zu vermeiden. In irgendeiner Probeklausur steht, dass das Worst-Case vermeiden kann.

Aber ich meine, mit einer Zahlenfolge aus den gleichen Elementen würde das nicht funktionieren und dann hätten wir das alte Worst-Case .

[Robert]

Aber ich meine, mit einer Zahlenfolge aus den gleichen Elementen würde das nicht funktionieren und dann hätten wir das alte Worst-Case .

Und warum nicht?

Auch bei einer Zahlenfolge, die nur aus den selben Elementen besteht, wird in der Rekursion die aktuell betrachtete Menge in zwei gleich große Mengen aufgeteilt. Man hat zwar viele Swaps in der Partition-Methode (an jeder Stelle), aber die äußere Schleife bricht ab, sobald sich die Indizes i und j überlaufen und für den Fall, dass man nur gleiche Elemente hat, ist das genau in der Mitte der Menge.
Denn die inneren While-Schleifen der Partition-Methode werden nie durchlaufen, es wird also in jedem Schritt der äußeren while-Schleife i um 1 erhöht und j um 1 erniedrigt.
Dadurch bekommst Du also auch bei Folgen, die keine unterschiedlichen Elemente enthalten, eine logarithmische Komplexität für die Anzahl der Vergleiche.

Das im QuickSort kommt ja nur dadurch zustande, dass diese Aufteilung bei sortierten (oder inverse sortierten) Folgen immer linear zerfällt und nicht logarithmisch, wenn man das rechte Elemente als Pivot wählt.
Denn im schlimmsten Fall wird die while i<j nur ein einziges mal durchlaufen, aber eine der inneren braucht immer O(n). Dann bekommt man das .
Nimmt man den Median als Pivot, so zerfällt die Menge immer in 2 gleichgroße Teile (+-1).

[LonliLokli]

Jo. Ich habe bei while-schleifen in partition die Bediengung missverstanden.

[NightmareVirus]

Auch bei einer Zahlenfolge, die nur aus den selben Elementen besteht, wird in der Rekursion die aktuell betrachtete Menge in zwei gleich große Mengen aufgeteilt. Man hat zwar viele Swaps in der Partition-Methode (an jeder Stelle), aber die äußere Schleife bricht ab, sobald sich die Indizes i und j überlaufen und für den Fall, dass man nur gleiche Elemente hat, ist das genau in der Mitte der Menge.

Wenn mich nicht alles täuscht läuft doch zuerst i nach rechts, bis es j erreicht hat. da j ganz rechts steht, überschneiden sie sich nicht in der Mitte sondern ganz rechts. und deswegen folgt O(n^2).

[LonliLokli]

Auch bei einer Zahlenfolge, die nur aus den selben Elementen besteht, wird in der Rekursion die aktuell betrachtete Menge in zwei gleich große Mengen aufgeteilt. Man hat zwar viele Swaps in der Partition-Methode (an jeder Stelle), aber die äußere Schleife bricht ab, sobald sich die Indizes i und j überlaufen und für den Fall, dass man nur gleiche Elemente hat, ist das genau in der Mitte der Menge.

Wenn mich nicht alles täuscht läuft doch zuerst i nach rechts, bis es j erreicht hat. da j ganz rechts steht, überschneiden sie sich nicht in der Mitte sondern ganz rechts. und deswegen folgt O(n^2).

Nein, i und j treffen sich in der Mitte, da in shcleifen nach echt grösser bzw. kleiner geprüft wird, werden die elemente zwar n/2 mal getauscht, dafür werden die partitionen logarithmisch klein(oder es werden genau zwei gleich grosse partitionen entstehen).