Sortieren...

maxi_muster

Hallo,

ich ein einen std::vector<particle> part mit folgenden Objekten.

struct particle
{
    [...]
    double collision_time;
}

Ich wuerde gerne alle Elemente aus meiner Liste part sortieren, so dass ich auf das Element zugreifen kann, welches die kleinste collision_time hat. Fallen euch Wege ein, die sinnvoller als der naive Ansatz sind, einfach alle Elemente des Vektors durchzugehen und sich das mit dem kleinsten rauszuschreiben?

Danke!

SeppJ

Was willst du denn jetzt? Das kleinste Element finden oder die ganze Liste sortieren? Egal wie die Antwort lautet, ist so eine Standardaufgabe nichts was man jedes mal selber neu programmiert. Da lässt man dann einfach std::min_element beziehungsweise std::sort drauf los.

Hier müsstest du natürlich noch entweder einen eigenen Vergleichsoperator, eine Vergleichsfunktion oder (mit C++0x) einen passenden Lambdaausdruck schreiben, damit du auch die collision_time im struct als Vergleichselement heranziehst. Keine Angst, das klingt kompliziert, ist aber ziemlich einfach und sollte in jedem Beispiel zu den Standardalgorithmen vorkommen.
edit: Kurz gesagt: Das was EOutOfResources im Beitrag unter mir zeigt.

EOutOfResources

Hier die Möglichkeiten:

//Als Operator (C++ & C++0x)
struct Particle
{
  //...
  double collision_time;
  //...
  bool operator< (const Particle& rhs) const
  {
    return this->collision_time < rhs.collision_time;
  }
  //...
}
std::sort(part.begin(), part.end());

//Als freie Vergleichsfunktion (C++ & C++0x)
bool ParticleLess(const Particle& lhs, const Particle& rhs)
{
  return lhr.collision_time < rhs.collision_time;
}
std::sort(part.begin(), part.end(), ParticleLess);

//Als Lambdafunktion (nur C++0x)
std::sort(part.begin(), part.end(), [](const Particle& lhs, const Particle& rhs) -> bool{return lhr.collision_time < rhs.collision_time;});

EDIT: Sofern ich dich richtig verstanden habe...

Bashar

maxi_muster schrieb:

Fallen euch Wege ein, die sinnvoller als der naive Ansatz sind, einfach alle Elemente des Vektors durchzugehen und sich das mit dem kleinsten rauszuschreiben?

Anders geht es wohl kaum. Wenn man sich auch nur ein Element nicht anguckt, könnte das ja gerade das kleinste sein.

Falls du aber immer wieder das kleinste haben willst, könnte es sich anbieten, die Partikel von vornherein in einer Priority Queue zu speichern. (=> Google, Wikipedia, etc.)

DocShoe

std::min_element und ein entsprechendes Funktionsobjekt/Vergleichsfunktion gingen auch, ohne dass die Liste sortiert werden müsste.

brotbernd

Ich weiß nicht genau was du da programmierst aber ich vermute mal, dass ein wirklich sinnvoller Algorithmus gar nicht alle collision_times berechnen muss um, das 'dichteste' Partikel zu finden.
Ansonsten wurden schon die richtigen Ansätze genannt, und das war nur ein kleiner Denkanstoß

maxi_muster

Danke fuer die vielen schnellen Antworten. Das war wohl etwas wirr, mit dem sortieren und kleinstem Element finden.

Ich schreibe hier gerade an einer Event-Driven-Simulation, Algorithmus ist einfach:

Finde die naechste Kollision
Bewege alle Teilchen
Update Kollisionsliste

Ich habe dann als ich die Frage gestellt habe festgestellt, das der naive Loesungsweg Ordnung N ja alles ist was ich brauche, und das es wohl kaum besser geht.
Es war halt aergerlich, weil ich versucht habe die Position in der particle liste selbst nicht zu veraendern. Sodass particle[1] durchweg particle[1] bleibt. Andererseits dachte ich, ich braeuchte eine sortierte Liste, die die naechsten Events beschreibt. Ich habe mir dann also eine zusaetzlichen Vector gemacht und da alle indizes eingetragen, und die sortieren wollen. Also so, dass an position 0 der index des particles steht, der die naechste Kollision hat. Und das war komplizierter als ich dachte...

Danke!

pumuckl

maxi_muster schrieb:

Ich habe mir dann also eine zusaetzlichen Vector gemacht und da alle indizes eingetragen, und die sortieren wollen. Also so, dass an position 0 der index des particles steht, der die naechste Kollision hat. Und das war komplizierter als ich dachte...

Solange du keine particles in deinen vector einfügst kannst du auch problemlos in deinem zweiten vector poitner statt der Indizes verwenden. Die lassen sich deutlich leichter sortieren (einfach dereferenzieren und den Wert dahinter als Sortierkriterium nehmen)

brotbernd

Kannst Du mir verraten was genau Du da simulierst? Ich mache ähnliche Sachen