Eigene Sortierfunktion übergeben

Funktionirt micht - aha

Ja, funktioniert nicht. Das ist ja das Problem.

Ich habe nun getrickst. Keine Ahnung, ob die Lösung gut ist.

template < typename MedianSort, typename OrderComparator >
  void partitionField(std::vector<T>* field,
                      const int leftIndex,
                      const int medianIndex,
                      const int rightIndex,
                      MedianSort medianSort,
                      OrderComparator orderSort)
  {
    auto leftIt = field->begin() + leftIndex;

    auto medianIt = field->begin() + medianIndex;

    // Ende ist bei std::partition() explizit, deshalb + 1
    auto rightIt = field->begin() + rightIndex + 1;

    std::sort(leftIt, rightIt, medianSort);

    std::sort(leftIt,       medianIt, orderSort);
    std::sort(medianIt + 1, rightIt,  orderSort);
  }

SeppJ

SortFunc schrieb:

Ich habe nun getrickst. Keine Ahnung, ob die Lösung gut ist.

Ich glaube nicht, dass dies den gewünschten Laufzeitanforderungen gerecht wird. Viel zu viel Sortiererei. Wenn du dich an die Vorgabe hältst, muss nur ein einziges Mal (beziehungsweise 2x, da für x und y) am Anfang sortiert werden.

Das ist mir bewusst, nur haben alle anderen Ansätze gescheitert und lieber benutze ich eine korrekte Lösung als eine falsche.

Irgendwie ist es total unnötig, dass du mindestens 4mal sortierst. Wenn du bereits einen der Vektoren nach den x-Koordinaten sortiert hast dann bist du doch eigentlich schon fertig. Der Median steht in der Mitte, alles kleinere links davon und die größeren Zahlen rechts. Da gibts es überhaupt gar nichts mehr zu partitionieren oder zu sortieren. Die anderen hier genannten Funktionen wie std::partition oder std::nth_elemnt sparen in bestimmten Situationen Zeit. Ein std::partition macht Sinn wenn du den Median bereits kennst (woher auch immer) und du nur an den unsortieren Partitionen interessiert bist. Über std::nth_elemnt kriegst du den Median und die Partitionen raus ohne den Vektor komplett zu sortieren.

Das Problem ist aber komplexer, siehe Seite 1 ganz unten.
Ich muss z. B. x nach dem Median von y partitionieren und dabei die X-Kleiner-Ordnung beibehalten.

Habs auch vorhin gemerkt. Mir ist auch noch ein Problem mit std::partition oder std::stable_partition aufgefallen. Wenn dir der y-Median bekannt ist und damit den x-Bereich partitionieren willst landet der Median in einer der Partitionen (je nachdem ob man < oder <= in der Vergleichsfunktion nutzt). Allerdings weiß man nicht wo dieser steht. Dank double kann man diesen auch nicht so einfach suchen (Vergleiche auf Gleicheit mit floating point Variablen sind böse). Ich würde dir daher wieder zu std::nth_element raten. Irgendwie ist sowieso das ganze hin und her mit den zwei Bereichen nervig, wird aber so von der Aufgabenstellung verlang...

Das Problem ist aber, dass std::nth_element die Ordnung nicht beibehält, deswegen hat es auch eine Laufzeit von O(n):
Siehe "Complexity"
http://en.cppreference.com/w/cpp/algorithm/nth_element

Wenn man die Ordnung beibehalten möchte, muss man sortieren und sortieren ist mind. n * log(n). Ich kann daher nicht glauben, dass die Angaben von meinem Prof. stimmen.

Welche Ordnung meinst du? Die der x-Elemente? Wird das irgendwo gefordert?

Ja, ich meine die der X-Elemente. Ob das gefordert ist? Naja, man soll rekursiv immer den Median nehmen – einmal den von y und damit x partitionieren und einmal den von x und damit y partitionieren. Median heißt aber: Sortiere und picke aus der Mitte.
Wenn du dir Beispiele aus kd-Bäumen anschaust (in meinem Fall 2D-Bäume), dann ist die Ordnung in den Beispielen auch immer beibehalten.

SeppJ

Halte dich doch einfach mal ganz genau an die Aufgabenstellung. Da ist doch alles Schritt für Schritt erklärt. Erfinde keine eigenen Sortierschritte oder Sonstiges.

@SeppJ:

Der Punkt ist: Die Kleiner-Ordnung geht hier in X1 und X2 ab diesem Schritt verloren:

- Partition X into two sequences X1 and X2, such that X1 contains the 
same points as Y1 and X2 the same points as Y2.

Damit könnte ich im nächsten Schritt nicht mehr den Median von X1 und X2 finden ohne vorher nach der X-Kleiner-Ordnung in den Partitionen zu sortieren.

SeppJ

SortFunc schrieb:

Der Punkt ist: Die Kleiner-Ordnung geht hier in X1 und X2 ab diesem Schritt verloren:

Wieso? Zum Partitionieren musst du doch nicht die Reihenfolge verändern.

Nach x sortiert:

X = { (1,4), (2,3), (3, 2), (4, 1) }

Nach y sortiert:

Y = { (4,1), (3,2), (2,3), (1,4) }

Median von Y: (3,2)

Y1 = { (4,1) }
Y2 = { (2,3), (1,4) }

Daraus folgt:

X1 = { (4,1) }
X2 = { (2,3), (1,4) }

X2 ist nun anders angeordnet und die Kleiner-Ordnung in X wird verletzt (könnte natürlich auch zufällig richtig angeordnet sein).

SeppJ

Du sollst nicht X1=Y1 und X2=Y2 sagen. In der Vorgabe steht du sollst X aufteilen, so dass X1 die gleichen Elemente wie Y1 enthält und ebenso für X2. Da X bereits sortiert ist, sind dann auch automatisch X1 und X2 sortiert.

@SeppJ: Hast du bedacht das man den Y-Median loswerden muss? Man kann zwar ein stable_partition machen aber dann steht der Y-Median an einer zufälligen Stelle.

Jup, genau das war mein Problem bei stable_partition, zumal der Worst Case eine Laufzeit von n * log n hat.

SeppJ

sebi707 schrieb:

@SeppJ: Hast du bedacht das man den Y-Median loswerden muss? Man kann zwar ein stable_partition machen aber dann steht der Y-Median an einer zufälligen Stelle.

Ja, das habe ich bedacht. Die Lösung ist einfach: Man muss nicht immer alles mit der Standardbibliothek lösen.

SortFunc schrieb:

Jup, genau das war mein Problem bei stable_partition, zumal der Worst Case eine Laufzeit von n * log n hat.

Nur, wenn du alles in-place machst. Wozu dich höchstens der Wunsch zwingt, Speicher sparen zu wollen. Diesen Wunsch ignorierst du. Geh einfach alle Elemente linear durch: In welcher Zielmenge ist ein Element? Das kannst du durch Vergleich mit dem Median herausfinden (und der Median selbst ist in keiner Zielmenge). Dann dieses Element hinten in der Zielmenge anhängen. Das sind N konstante Vergleiche und N-1 konstante Kopien (oder Verschiebungen), also insgesamt O(N). Oder mach keine neuen Mengen, sondern sortier die alten um und mach eine Sonderbehandlung für den Median. Sollte auch in O(n) gehen.

Hm, stimmt. Ich war auf dem Holzweg, weil mein Prof. sagte, dass er alles in-place macht, was für O(n) eigentlich kaum stimmen kann.

Werde ich mal als letztes ausprobieren, wenn die Aufgabe quasi funktional fertig ist.

Danke!