Eigene Sortierfunktion übergeben

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!

DocShoe

Mit diesem Algo geht das geht doch in-place mit O(n), oder täusche ich mich da?

vector<QPoint> Data;

void f( 
{
   auto Median = determine_median( Data );
   auto Left  = Data.begin();
   auto Right = Data.end() -1;

   while( Left < Right )
   {
      if( *Left >= Median )
      { 
         // Element ist größer-gleich als der Median und wird mit dem aktuell 
         // letzen unbehandelten Element vertauscht. Das aktuell letzte 
         // Element steht jetzt am aktuellen Anfang und wird im nächsten
         // Schleifendurchlauf behandelt.
         swap( *Left, *Right );
         --Right;
      }
      else
      {
         // aktuelles Element ist kleiner als der Median und muss nicht
         // behandelt werden.
         ++Left;
      }
   }
}

Danke, für deine Lösung!
Wenn ich deinen Algorithmus richtig verstehe, dann ist nicht definiert, wo der Median nach der Partitionierung steht, richtig? Das wäre aber bei meinem Algorithmus fatal, weil der Median entweder in der Mitte stehen sollte, so dass ich ihn über Indizes entsprechend ausklammern kann oder er sollte komplett rausfallen.

Ich habe die Lösung von SeppJ genommen. Hier ist mir aufgefallen, dass durch die Rekursion evtl. die jeweiligen Partitionierungen lange gehalten werden und da das alles Kopien sind, evtl. viel Speicherplatz benötigt wird.

Es gibt eben keine perfekte Lösung, aber dennoch danke an alle, die sich beteiligt haben!

SortFunc schrieb:

Ich habe die Lösung von SeppJ genommen. Hier ist mir aufgefallen, dass durch die Rekursion evtl. die jeweiligen Partitionierungen lange gehalten werden und da das alles Kopien sind, evtl. viel Speicherplatz benötigt wird.

Wobei: Wenn man Referenzen und keine Kopien einfügt, hat man das Speicherplatzproblem auch nicht mehr...