Reihenfolge des Vorlaufens der Indizes bei Pivot Partitioning

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Reihenfolge des Vorlaufens der Indizes bei Pivot Partitioning

Beitrag von LukasPhysiker » 13. Mai 2017 22:59

Ich bin gerade am Verzweifeln, die Nabla-Aufgabe für das Pivot-Partitioning richtig zu lösen.

Da ich am Montag mein Testat habe und wir die meisten der Nabla-Aufgaben noch gar nicht in der Vorlesung hatten (dazu erstmal WTF??) habe ich mit an den Videos in der Videothek Algorithmik orientiert, in diesem Fall also an diesem Video: https://www.youtube.com/watch?v=9b_B17MXRG0

Da sieht es so aus, als ob zuerst der Index i1 nach rechts läuft, bis man ein Element findet, das nicht kleiner als der Pivot ist. Dann wird das Element in die richtige Sektion vertauscht und i1 läuft weiter, falls das reingetauschte Element nun richtig ist und i2 bzw. i3 läuft automatisch weiter, da ja ein richtiges Element dort reingetauscht wurde. Ich dachte, das läuft jetzt so weiter, bis i1 ganz rechts angekommen ist, dann übernimmt i2, dann i3.

Ich habe zwar schon rausgefunden, dass Nabla unter einer "Iteration" eine Vertauschung, nicht ein Weiterrücken des Indizes sieht, aber die Reihenfolge der Vertauschungen scheint mir vollkommen willkürlich wie sie die Nabla-Lösung darstellt! Dadurch scheitern auch jedes Mal meine Versuche!

Kann mir bitte jemand erklären, nach welcher Logik das Nabla-Skript vorgeht?

Benutzeravatar
LordMaddhi
Nichts ist wie es scheint
Beiträge: 23
Registriert: 20. Apr 2017 11:57
Wohnort: Darmstadt, Hessen

Re: Reihenfolge des Vorlaufens der Indizes bei Pivot Partitioning

Beitrag von LordMaddhi » 14. Mai 2017 17:32

Es geht wie folgt:
Als "Iteration" wird nur das Vertauschen gezählt, nicht die Schritte die die "is" machen.

- Steht i1 auf einem Element > Pivot und i3 auf einem Element <= Pivot, so wird getauscht (Iteration + 1; danach rückt i1 auf das nächste Element >= Pivot und i3 auf das nächste Element <= Pivot)

- Steht i1 auf einem Element = Pivot und i2 auf einem Element != Pivot, so wird getauscht (Iteration + 1; i1 bleibt auf dem Element (sofern > Pivot, sonst rückt es weiter an das nächste Element >= Pivot) und i2 auf das nächste Element != Pivot)

- Steht i3 auf einem Element = Pivot und i2 auf einem Element != Pivot, so wird getauscht (Iteration + 1; i2 rückt auf das nächste Element != Pivot und i3 bleibt auf dem Element (sofern < Pivot, sonst rückt es weiter an das nächste Element <= Pivot)

- gibt es beim Vorrücken kein weiteres Element mit: >= Pivot (i1), != Pivot (i2), <= Pivot (i3) so rückt das i auf die Endposition (i1 -> m1; i2 -> m2; i3 -> Länge+1)

- sobald 2 der 3 "is" auf Endpositionen sind, ist der Algorithmus zu Ende (bzw. wird danach rekursiv auf die Teilbereiche < Pivot und > Pivot aufgerufen)
Ich bin nicht die Signatur. Ich putze hier nur.

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: Reihenfolge des Vorlaufens der Indizes bei Pivot Partitioning

Beitrag von LukasPhysiker » 14. Mai 2017 19:30

Danke, mit der Erklärung habe ich gerade drei Tests hintereinander bestanden! Damit glaube ich, dass ich es jetzt richtig verstanden habe.

Benutzeravatar
LordMaddhi
Nichts ist wie es scheint
Beiträge: 23
Registriert: 20. Apr 2017 11:57
Wohnort: Darmstadt, Hessen

Re: Reihenfolge des Vorlaufens der Indizes bei Pivot Partitioning

Beitrag von LordMaddhi » 15. Mai 2017 13:19

Freut mich :P
Ich bin nicht die Signatur. Ich putze hier nur.

Antworten

Zurück zu „Archiv“