Seite 1 von 1

Pivot partitioning by scanning: Invariante

Verfasst: 3. Mai 2016 22:24
von jr29zyni
Guten Tag,

EDIT: Hat sich erledigt; 8,9,10 der Implementation stellen das ja sicher. :oops:

ich habe eine Verständnisfrage zum AlgoWiki-Eintrag "Pivot partitioning by scanning".
Ich verstehe nicht, warum die Aussagen jeweils hinter dem Semikolon (s. Anhang 1, bei 2., 3. und 4.) richtig sind.
Es ist doch auch möglich, dass der Wert, auf den der Zeiger i1/i2/i3 zeigt, auch schon im richtigen Bereich steht. Widerspricht dies nicht der jeweiligen Aussage hinter dem Semikolon?
Konkret glaube ich, ein Gegenbsp. gefunden zu haben, siehe i1 im Anhang 2. Dort ist p=3 und S[i1]=1 und i1 < m1, aber \(S[i1] \nless p\) gilt nicht.

Freundliche Grüße

Re: Pivot partitioning by scanning: Invariante

Verfasst: 4. Mai 2016 06:38
von Prof. Karsten Weihe
jr29zyni hat geschrieben: EDIT: Hat sich erledigt; 8,9,10 der Implementation stellen das ja sicher.
Ich denke (und hoffe, Sie stimmen mir zu), dass dies ein gutes Beispiel dafür ist, wie die Invariante das Verständnis des Codes unterstützt, insbesondere die Überprüfung, ob der Code tatsächlich das tut, was er soll. 8)

KW