Quicksort mit median pivotisierung?

Hey, ich habe den Quicksort Algorithmus folgendermaßen beschrieben bekommen:

Nun habe ich eine Methode lowerMedian(), die den Median einer Liste bestimmt. Wie genau muss ich diese Methode nun im Quicksort algorithmus einsetzen, damit dieser als Pivot Element immer den Median nimmt, die Laufzeit also O(log(n)) ist?

Answer 1

[PWolff]

(Bitte Quellcode nicht nur als Bild, sondern auch als Text posten - dafür gibt es in der Formatierungsleiste das Symbol </>)

Der genannte Algorithmus nimmt das ganz linke Element als Pivot-Element:

x = A[l];

Falls lowerMedian nur den Wert, nicht aber die Position liefert, musst du die Liste noch nach dem Median-Wert durchsuchen, um die Position zu erhalten. Nennen wir die Variable für die Position des Medians mal 0.

Wie Quicksort mit Pivot-Element in der Mitte arbeitet (wenn überhaupt), müsste ich recherchieren. Also schlage ich vor, am Anfang A[l] und A[m] zu tauschen und dann ab

i = l + 1;

fortzusetzen.

(Aber wie funktioniert die Median-Bestimmung überhaupt? Kriegt man so was ohne vorherige Sortierung mit Laufzeitkomplexität unter O(n) hin?)

Woher ich das weiß: Hobby – Hobby, Studium, gebe Nachhilfe