Übungsblatt zur Klausur A3

[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

[Stephoogle]

Die passiert bei i=1.
Implementation: 2.2.1

[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

[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.

[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 )