Eigene Sortierfunktion übergeben

Verflixt und zugenäht! Ich komme einfach auf keine schöne Lösung!

template < typename Comparator >
  void partitionField(std::vector<T>* field, int leftIndex, int rightIndex,
                      int medianIndex,
                      Comparator comp)
  {
    auto left = field->begin();
    std::advance(left, leftIndex);

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

    std::nth_element(left, medianIndex, right, comp);
  }

void bla() {
    // ...
    partitionField<LessYComparator>(x, leftIndex, medianIndex, rightIndex, LessYComparator());
}

Fehler: no matching function for call to 'nth_element'
    std::nth_element(left, medianIndex, right, comp);
    ^~~~~~~~~~~~~~~~

Bei std::vector braucht man std::advance nicht unbedingt und kann direkt auf die Iteratoren was addieren. Es compiliert gerade nicht weil dein medianIndex ein int ist und kein Iterator. Dein vorheriges Beispiel hat nicht compiliert weil du deine const Lambda Funktion an eine non-const Reference binden wolltest. Ließ mal etwas aufmerksamer die Fehlermeldungen.

Ja, das mit dem Iterator ist mir auch gerade aufgefallen. Versuche mich seit über 1 h daran und verliere gerade die Geduld.

Jedenfalls danke! Scheint erst mal zu funktionieren!

Und bitte die explizite Angabe des Template Parameters entfernen. (Informativer und unterhaltsamer Vortrag dazu: Don’t Help the Compiler)

Sorry, Jungs, ich krieg das einfach nicht hin. Mein Ansatz funktioniert nicht und erreicht möglicherweise auch nicht die geforderte Laufzeit.

Folgendes soll reicht werden:

- Sort all points both by x- and y-coordinates
    => Two sorted sequences X and Y.

- Subdivide Y at its median and take it as the root of the tree
    => Two sub-sequences Y1 and Y2

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

- Partition X1 and X2 recursively at the median and subdivide Y1 and Y2
accordingly as above, until these sequences contain only one point.
    - These points are the leafs of the tree.

Dabei soll das Partitionieren in O(n) geschehen.

void partitionField(std::vector<QPointF>* field,
                    const int leftIndex,
                    const int rightIndex,
                    const std::function<int(QPointF)>& medianCompare)
  {
    auto leftIt = field->begin() + leftIndex;

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

    std::stable_partition(leftIt, rightIt, medianCompare);
  }

Dummerweise funktioniert das mit folgender Sort-Funktion nicht:

const auto compare = [yMedian](const QPointF& point) {
    return point.y() < yMedian.y();
  };

Compilierfähiger Code ist hier zu finden:

https://ideone.com/MZoeBL

Habe extra die Qt-Klasse QPointF abgebildet, damit das dort läuft.

Jemand eine Idee?!

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).