Eigene Sortierfunktion übergeben

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