Seite 1 von 1

Übungsblatt zur Klausur A3

Verfasst: 21. Sep 2013 02:11
von pirate07
Hallo,

ist die Musterlösung von Aufgabe A3 richtig?

Nach welcher regeln ist die 40 an i2 gekommen?????

Kann jemand vielleicht bitte seine lösung hochladen.
lg

Re: Übungsblatt zur Klausur A3

Verfasst: 21. Sep 2013 08:41
von Stephoogle
Die passiert bei i=1.
Implementation: 2.2.1

Re: Übungsblatt zur Klausur A3

Verfasst: 21. Sep 2013 10:45
von pirate07
Also nach Wiki
S[i1] > p-wert
tausche S[i1] mit S[i3] d.h 40 wird mit 18 getauscht oder aber ich es falsch verstanden?

danke

Re: Übungsblatt zur Klausur A3

Verfasst: 21. Sep 2013 10:54
von brjan
Das sehe ich auch so. Der Tausch der 40 mit der 23 dürfte gar nicht passieren, da i3 nicht auf Index 12, sondern auf Index 14 initialisiert werden müsste (Induction Basis, Implementation, Schritt 10).

Das wäre in anderen Worten auch eine Verletzung der Invariante bei i=0, denn die Pointer dürfen ja nicht auf final gesetzte Elemente zeigen (solange sie ihre Partition noch nicht abgelaufen haben).

Bei mir terminiert der Algorithmus nach 5 Iterationen.

Grüße.

Re: Übungsblatt zur Klausur A3

Verfasst: 21. Sep 2013 13:00
von D.Wilhelmi
In meiner Lösung termininiert der Algorhitmus ebenfalls nach 5 Iterationen, ich vermute das in der Lösung die Schritte 8-10 der Iterationsbasis nicht gemacht wurden. Aber selbst unter diesen Vorraussetzungen bleibt noch die Frage, warum i2 in der Lösung auf Position 13 zeigt und nicht auf Position 12. So wie ich den Algorithmus verstehe kann ein Pointer ja nur erhöht werden, nach einem Tausch (für i2: Induction Step 2.1.2, 3.2) oder während der Initialisierung des Algorithmus (für i2: Induction Basis 9). Da beides bis zum Element Nr. 8 ja nicht stattfindet, sollte i2 auf 9 zeigen. (Scheint ein Tippfehler zu sein, da auch 22 und 9 getauscht werden, und nicht 22 und 40 ;) )