Teilprobleme im Verhältnis 9:1 zerlegen

09.08.2014, 17:53

evinda

Teilprobleme im Verhältnis 9:1 zerlegen

Hallo!!! Wink

Wie kann ich die Rekursion finden,die die Komplexität vom Algorithmus Quicksort beschreibt,wenn wir die Teilprobleme im Verhältnis 9:1 zerlegen?

Der Algorithmus ist der folgende:

code:
1: 2: 3: 4: 5:	Quicksort(A,p,r) if p<r then q<- partition(A,p,r) Quicksort(A,p,q-1) Quicksort(A,q+1,r)

10.08.2014, 01:03

Auf diesen Beitrag antworten »

ed209

Hi

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?

Gruß,
ED

10.08.2014, 01:16

Auf diesen Beitrag antworten »

evinda

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

Neue Frage »

Antworten »

Teilprobleme im Verhältnis 9:1 zerlegen

Verwandte Themen