aufgabe 7

[michaelh]

im skript auf seite 36 wird der algo6 quicksort in der zeile 4 und 5 rekursiv aufgerufen. der aufruf in zeile 5 kann ja nicht erfolgen, da vorher immer der quicksort von zeile 4 aufgerufen wird!

bitte um hilfe

[Phistomefel]

Hallo,
so wie ich das sehe sind die beiden Aufrufe in einem If und rekursiv.
D.h. das der erste Aufruf (Quicksort(A,l,p-1)) solange rekursiv ausgeführt wird, bis die Bedingung (l<r) nicht mehr erfüllt ist. Das gleiche passiert anschliessend mit dem 2. Aufruf von Quicksort.

[marioana]

Hallo,
so wie ich das sehe sind die beiden Aufrufe in einem If und rekursiv.
D.h. das der erste Aufruf (Quicksort(A,l,p-1)) solange rekursiv ausgeführt wird, bis die Bedingung (l<r) nicht mehr erfüllt ist. Das gleiche passiert anschliessend mit dem 2. Aufruf von Quicksort.

ich seher hier kein if
ausser in der ersten zeile!
und ist dieses if erfüllt, so wird dann immer zeile 4 aufgerufen.

da müssten dann 2 if sein -eines vor zeile 4 und eines vor zeile 5 ....

[Phistomefel]

Also die Funktion Quicksort bildet eine rekursive Funktion mit der Abbruchbedingung l>=r. In Zeile 4 ruft sich Quicksort selbst wieder auf. Das passiert dann solange bis irgendwann die Abbruchbedingung l>=r erfüllt ist. Anschließend läuft das Programm bei dem "aufrufendem" Quicksort in Zeile 5 weiter, wo wieder eine Rekursion mit anderen Parametern gestartet wird.

[spjoe]

wir gehen das erste mal in die partition mit l=1 r=8
<44 55 12 42 94 18 06 67> pivot = r = [8] = 67
zuerst i solange von links nachrechts gehen bis ein kleiners element als das pivot element kommt. in dem Fall [1] = 44, dann mit j von recht nach links solane gehen bis größeres element kommt [5] = 94
da j > i verstausch (44 mit 94 vertauschen)
<94 55 12 42 44 18 06 67>
wieder mit i solange gehen bis kleiners als pivot gefunden [2] = 55, dann mit j weiter bis größeres gefunden oder j<=i dann abruch (in dem fall weil das nächste größere wäre 94
jetzt [i] mit [r] vertauschen ([2] mit [8]
<94 67 12 42 44 18 06 55>
i als p=2(der teiler) zurückgeben
linkepartition (1.quicksort) aufrufen mit den werten (A,l,p-1) -->(A,1,1) wird sofort abgebrochen weil l>=r
so rechtepartition mit (l=3, r=8)
<94 67 12 42 44 18 06 55> i bleibt bei 12 stehen j geht bis i somit abruch [i] mit [r] vertauschen 55 mit 12
<94 67 55 42 44 18 06 12>
P=3
linkepartition l=3 r =2 --> ende
rechtepartition l=4 r = 8
<94 67 55 42 44 18 06 12> i bleibt bei 06 stehen j geht über i hinaus --> abruch schleife [i] [r] vertauschen 12 mit 6
<94 67 55 42 44 18 12 06>
P=7
linkepartiton l = 4 r=6 pivote = 18
i bleibt erst bei 18 steh (darum im algo <= x!! damit man nicht über das pivot elemnt drüber kann!!!)somit i > j --> [i] mit [r] vertauschen 18 mit 18 vertauschen
<94 67 55 42 44 18 12 06>
<94 67 55 42 44 18 12 06>
p=6
linkepartion l = 4 r =5
i bleibt bei 42 stehen i >= j --> vertausche [i] mit [r] --> 42 mit 44
<94 67 55 42 44 18 12 06>
<94 67 55 44 42 18 12 06>
linke und rechte partiion ende
rechte partition l= 7 r = 6 ende
rechtepartiton l = 8 r = 8 --> ende

<94 67 55 44 42 18 12 06>

hoff hab mich nirgend vertippt
lg spjoe

[Ali K]

Wow, danke für die Mühe hat sehr geholfen beim Verständnis des algorithmus. Einzige Frage hab ich nur zu dem letzten Teil:

Am Ende hast du l=7, r=6 und l=8, r=8



i bleibt bei 42 stehen i >= j --> vertausche [i] mit [r] --> 42 mit 44
<94 67 55 42 44 18 12 06>
<94 67 55 44 42 18 12 06>
linke und rechte partiion ende
rechte partition l= 7 r = 6 ende
rechtepartiton l = 8 r = 8 --> ende

<94 67 55 44 42 18 12 06>

hoff hab mich nirgend vertippt
lg spjoe

Meine konkrete Frage eigentlich, wenn die Liste nun vollständig sortiert ist, checkt das der algorithmus ja durch die Indexgrenzen...weiss aber leider nicht wie du auf die 7/6 bzw. 8/8 kommst :confused:

ich denke so: nach dem Vertauschen von 44 und 42 ist p=4 .. dann ergibt sich für linke partition l=4, r=3 und für die rechte l=5, r=5 --> beide nix machen --> fertig !

blick da nicht so toll durch leider

[Lillipip]

Ich hätte das so irgendwie gemacht:

i=l-1; j=r;
wiederhole
wiederhole
i=i+1;
bis A[i].key (kleiner gleich) x;
wiederhole
j=j-1;
bis A[j].key (größer gleich) x;
falls i < j dann {
vertausche A[i] und A[j];
}
bis i (größer gleich) j;
vertausche A[i] und A[r];
retourniere i;

Was sagt ihr dazu?

[spjoe]

Wow, danke für die Mühe hat sehr geholfen beim V

ich denke so: nach dem Vertauschen von 44 und 42 ist p=4 .. dann ergibt sich für linke partition l=4, r=3 und für die rechte l=5, r=5 --> beide nix machen --> fertig !




jop genau
das hab ich mit >>linke und rechte partiion ende<< angedeuten, die anderen 2 rechten partition sind noch von früher über (rekursion)

lg spjoe

[tonico]

Ich hätte das so irgendwie gemacht:

i=l-1; j=r;
wiederhole
wiederhole
i=i+1;
bis A[i].key (kleiner gleich) x;
wiederhole
j=j-1;
bis A[j].key (größer gleich) x;
falls i < j dann {
vertausche A[i] und A[j];
}
bis i (größer gleich) j;
vertausche A[i] und A[r];
retourniere i;

Was sagt ihr dazu?

Sollte passen, nur in der zweiten Ungleichung fehlt die Zusatzbedingung j <= i damit das j links nicht "raushüpfen" kann (vgl. Skriptum).

[marioana]

<94 67 55 44 42 18 12 06>

hoff hab mich nirgend vertippt
lg spjoe


thx! hat mir wirklich geholfen - nun ist das beispiel 7 und auch das beispiel 8 klar! :thumb:

[Lillipip]

Sollte passen, nur in der zweiten Ungleichung fehlt die Zusatzbedingung j <= i damit das j links nicht "raushüpfen" kann (vgl. Skriptum).

Könntest du mir das in Farbe reinschreiben, weiss so nicht genau, was du meinst...
THX

[tonico]

Könntest du mir das in Farbe reinschreiben, weiss so nicht genau, was du meinst...
THX
Nein eher nicht :), aber du könntest nochmal Deinen Code mit dem im Skriptum vergleichen, speziell die Zeilen die in Deinem Code fetten Text enthalten.

[Lillipip]

Hab das SS06 Skriptum... da steht das genau so drinnen, nur dass ich die Zeichen (fett) umgedreht hab.

[Lillipip]

Zur Veranschaulichung hab ich das hier gefunden...
http://olli.informatik.uni-oldenburg.de/fpsort/QuickAnimation.html

[tonico]

Hab das SS06 Skriptum... da steht das genau so drinnen, nur dass ich die Zeichen (fett) umgedreht hab.

Achso, das wusste ich nicht, na in meinem Skriptum von SS07 steht bis j <= i oder A[j].key <= x;

[ScherlOMatic]

wie kommt man auf die linke Indexgrenze?

thx

[Silent_Bob]

Versteh ich das richtig daß bei vertauschen von >= und <= die Ordung sich umdreht. A[i]Key >= x wie im Skriptum WS 07 sortiert von kleinstem Element vorne bis zum größten Element hinten, und A[i]Key <= x sortiert umgekehrt.

[michaelh]

linke und rechte partiion ende
rechte partition l= 7 r = 6 ende
rechtepartiton l = 8 r = 8 --> ende

<94 67 55 44 42 18 12 06>

hoff hab mich nirgend vertippt
lg spjoe

warum 2 mal rechte partition ende?? kannst du das nochmals erklären??