Pivot Partitioning by Scanning - unbehandelter Fall?

dominik_andreas
Erstie
Erstie
Beiträge: 18
Registriert: 21. Mai 2012 15:07

Pivot Partitioning by Scanning - unbehandelter Fall?

Beitrag von dominik_andreas »

Hallo,

ich bin bei der Bearbeitung der Aufgabe 2 der 5. Übung auf einen Fall gestoßen, der glaube ich im Wiki nicht behandelt wird.
In meinem erstellten Beispiel kam ich zu dem Punkt wo:
  • i1 an der Stelle m1 steht
  • i2 noch nicht an der Stelle m2 steht
  • i3 an der Stelle n+1 steht
Nun wird ja gemäß dem Wiki S[i2] mit S[i3] getauscht, da i1=m1 (und i2!=m2) ist. Danach wäre der Algorithmus in meinem Fall beendet, allerdings würde der Zugriff auf S[i3] einen Fehler verursachen, da i3=n+1 ist und damit keine gültige Stelle in der Liste mehr ist.

Mich interessiert ob ich da vielleicht etwas falsch verstanden habe oder dieser Fall tatsächlich nicht im Wiki behandelt wird.
Meine Inputsequenz ist übrigens [a,x,m,y,m,b,z], m1=3, m2=6.
Der vorletzte Zustand der Liste ist bei mir [a,b,m,y,m,x,z], i1=3,i2=4,i3=8

jan789
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 10. Apr 2012 21:38

Re: Pivot Partitioning by Scanning - unbehandelter Fall?

Beitrag von jan789 »

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

Patrick.Lerner
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 5. Aug 2011 04:51
Wohnort: Lautertal, Kreis Bergstraße
Kontaktdaten:

Re: Pivot Partitioning by Scanning - unbehandelter Fall?

Beitrag von Patrick.Lerner »

dominik_andreas hat geschrieben:
  • i1 an der Stelle m1 steht
  • i2 noch nicht an der Stelle m2 steht
  • i3 an der Stelle n+1 steht
Nun wird ja gemäß dem Wiki S[i2] mit S[i3] getauscht, da i1=m1 (und i2!=m2) ist. Danach wäre der Algorithmus in meinem Fall beendet, allerdings würde der Zugriff auf S[i3] einen Fehler verursachen, da i3=n+1 ist und damit keine gültige Stelle in der Liste mehr ist.
Wenn du deine m's richtig gewählt hättest kommt der Fall nicht vor. Dein Beispiel ist im Prinzip: 1. Bereich ist fertig, 3. Bereich ist fertig, aber 2. noch nicht. Das gibt es einfach nicht, entweder der 1. oder der 3. muss dann auch noch unfertig sein.

In deinem Fall ist m_2 falsch sofern ich das sehe. Müsste wohl 5 sein, nicht 6.
:() { :|:& }; :

dominik_andreas
Erstie
Erstie
Beiträge: 18
Registriert: 21. Mai 2012 15:07

Re: Pivot Partitioning by Scanning - unbehandelter Fall?

Beitrag von dominik_andreas »

Ah, da lag der Fehler! Besten Dank :)

Antworten

Zurück zu „Archiv“