Übungsblatt zur Klausur A3

pirate07
Erstie
Erstie
Beiträge: 17
Registriert: 29. Jan 2007 12:01
Wohnort: Darmstadt

Übungsblatt zur Klausur A3

Beitrag 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

Stephoogle
Neuling
Neuling
Beiträge: 10
Registriert: 10. Sep 2013 15:43

Re: Übungsblatt zur Klausur A3

Beitrag von Stephoogle »

Die passiert bei i=1.
Implementation: 2.2.1

pirate07
Erstie
Erstie
Beiträge: 17
Registriert: 29. Jan 2007 12:01
Wohnort: Darmstadt

Re: Übungsblatt zur Klausur A3

Beitrag 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

brjan
Erstie
Erstie
Beiträge: 20
Registriert: 28. Jul 2011 12:21

Re: Übungsblatt zur Klausur A3

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

D.Wilhelmi
Neuling
Neuling
Beiträge: 3
Registriert: 16. Sep 2013 12:16

Re: Übungsblatt zur Klausur A3

Beitrag 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 ;) )

Antworten

Zurück zu „Archiv“