Informatiker Board | Druckvorschau: Teilprobleme im Verhältnis 9:1 zerlegen

Geschrieben von evinda am 09.08.2014 um 17:53:

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)

Geschrieben von ed209 am 10.08.2014 um 01:03:

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

Geschrieben von evinda am 10.08.2014 um 01:16:

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