Seite 1 von 1

Lösungsstrategien für Foo #3

Verfasst: 17. Jun 2015 00:38
von ek65baze
Pivot Partitioning

Zuerst zählt ihr die Anzahl aller Elemente die kleiner sind als der Pivot, dann sucht ihr nach Elementen die dem Pivot gleich sind.
Dann könnt ihr die Liste in 3 Subarrays aufteilen.

Beispiel:

Felder * Anzahl kleiner wie Pivot | Felder * Anzahl gleich Pivot | Felder * Anzahl größer Pivot

Sollte es keine Elemente geben die gleich dem Pivot sind so gibt es keinen mittleren Bereich und der Pointer von i2 kann auf
den Anfang der Felder * Anzahl größer Pivot gesetzt werden. (Dieser verändert sich nicht mehr)

Ansonsten werden die Pointer von i1,2,3 auf jeweils den Anfang jedes Subarrays gesetzt.
Also:

i1 = Feld 1 von Felder * Anzahl kleiner wie Pivot
i2 = Feld 1 von Felder * Anzahl gleich Pivot
i3 = Feld 1 von Felder * Anzahl größer Pivot

Nun wird in jedem Iterationsschritt für jeden Pointer geprüft ob der jeweilige Wert im richtigen Teilarray sitzt, sollte das stimmen bewegt sich der Pointer bis zum nächsten Element
das nicht in das Teilarray passt. Anschließend werden die Elemente 2er Pointer getauscht wenn diese in das gegenseitige Teilarray passen.

Binary Search Tree: Traverse

Die Schwierigkeit bei dieser Aufgabe ist sich zu merken in welchem Iterationsschritt man sich befindet, ich finde hier Stift und Papier sehr hilfreich.

Ihr beginnt mit dem 0. Iterationsschritt indem ihr das oberste Element in den Stack eintragt.
Die erste Zahl ist der Knoten, die zweite wie viele Zweige schon angesehen wurden.
Also:

(Zahl des Knotens, Zahl der angesehen Zweige)

Regeln:
1. Links vor Rechts.
2. Bei jedem IS den neuen Knoten mit einer 0 in den Stack eintragen (1 IS)
3. Bei (Knoten,1) wird dieser zu L hinzugefügt. (1 IS)
4. Bei (Knoten,2) wird dieser im nächsten IS entfernt. (1 IS)
5. Es wird immer nur der unterste Knoten im Stack verändert.
3. Gibt es keinen linken Zweig, wird der letzte Knoten zu (Knoten,1) geändert.
4. Nun nach Rechts gehen und wiederholen, gibt es keinen rechten Zweig wird der letzte
Knoten auf (Knoten,2) geändert.
5. Wenn ein Knoten gelöscht wird geht ihr einen Knoten nach oben und inkrementiert diesen um 1.

Wenn ihr diese Regeln befolgt solltet ihr das richtige Ergebnis herausbekommen.
*IS = Iterationsschritt

Wenn ihr Fehler bemerkt bitte unten drunter schreiben!

Re: Lösungsstrategien für Foo #3

Verfasst: 17. Jun 2015 14:01
von ttt3
Vielen Dank!

Nur eine kleine Anmerkung: Bei Pivot Partitioning werden ganz am Anfang (Iteration 0) die Zeiger nicht pauschal auf Feld 1 der einzelnen Subarrays gesetzt, sondern auf den ersten nicht passenden Wert. Also beispielsweise im Subarray x < Pivot auf das erste Feld mit dem Wert x >= Pivot. :)

Re: Lösungsstrategien für Foo #3

Verfasst: 17. Jun 2015 15:28
von prox
Hey Top !! Danke für deine Mühe :D

Re: Lösungsstrategien für Foo #3

Verfasst: 18. Jun 2015 04:24
von h_ar
Danke! :D