Ehrlich gesagt verstehe ich deine Frage nicht, was meinst Du mit "Rekursion finden"?
Auch verstehe ich die Schreibeweise des Algorithmus nicht: Was bedeutet " q<- partition(A,p,r)"?
Kannst Du die Funktionsweise des Algorithmus mit eigenen Worten wiedergeben?
Ich will die Rekursionsgleichung finden,mit der ich die Komplexität vom Algorithmus berechnen kann,angenommen wir zerlegen die Teilprobleme im Verhältnis 9:1.
Die Implementierung der Funktion "partition" teilt das Feld so, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen.
Die Funktion ist die folgende:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
partition(A,p,r)
x<-A[r]
i<-p-1
for j<-p to r-1
if A[j]<=x then
i<-i+1
A[i]<->A[j]
A[i+1]<->A[r]
return i+1
