SvenInfo12
Grünschnabel
Hallo, ich will die Korrektheit von folgendem Algorithmus zeigen. Es geht um die Medianbestimmung eines Feldes A mit n Zahlen unter Verwendung der Partition-Methode von Quicksort.
Nach Anwendung der Methode Partition auf den Bereich l bis r stehen von l bis q alle Elemente kleiner als A[q] bzw. in q+1 bis r alle Elemente größer als A[q].
Brauche ich für den Korrektheitsbeweis eine Invariante?
Ich komme leider nicht weiter. Ein kleiner Tipp würde schon sehr helfen
Java:
n=[n+1/2]
l=1
r=n
while(r<=n) do
q=partition(A,l,r)
if q=m then
return A[q]
else
if q>m then
r=q-1
else
l=q+1
Brauche ich für den Korrektheitsbeweis eine Invariante?
Ich komme leider nicht weiter. Ein kleiner Tipp würde schon sehr helfen