dominik_andreas hat geschrieben:Meine Inputsequenz ist übrigens [a,x,m,y,m,b,z], m1=3, m2=6.
Hi,
hier steckt, denke ich, schon der 1. Fehler drin... zumindest, wenn "m" dein "p" ist, wovon ich aber mal start ausgehe.
m1=3 ist vollkommen in Ordnung, da "a" und "b" zwei Elemente sind, die kleiner p sind. Allerdings macht m2=6 keinen Sinn.
Wenn m1 ermittelt wurde, ist im nächsten Schritt:
m2=m1=3
Dann werden Vorkommen von p=m gesucht. In diesem Fall sind das 2. D.h., m2 würde um 2 erhöht.
Dann ist m2=5 und nicht m2=6...
Der Rest ergibt sich dann in den weiteren Iterationen des Induktionsschrittes. Generell kann übrigens nie(!!!) der Fall auftreten, dass nach einer Iteration zwei Zeiger am Ende ihres Bereichs stehen und der dritte noch nicht (vgl. Korrektheitsbeweis im Wiki). Dies wäre unlogisch, da dann zwei Bereiche existieren würden, die ihre Elemente vollständig haben und ein dritter, der noch ein Element besitzt, welches in einen anderen Bereich gehört. Aber wo sollte dieses dann hinkommen? D.h., dass, wenn nur noch zwei Bereiche übrig sind, es immer eine gerade Zahl von zu vertauschenden Elementen geben muss, damit die Rechnung am Ende aufgeht.
Hoffe, das hilft ein wenig weiter
...
Gruß
Jan
