c++.de :: Vektor sortieren

ands Mitglied 22:22:54 15.05.2012 Titel:

Hallo zusammen

Ich versuche mich gerade an Kruskals Algorithmus um ein Netzwerkproblem zu lösen.

Meine Frage: Wie kann ich einen Vektor sortieren?
Und zwar ist es ein Vektor folgender Form " vector<Edge*> " wobei jede Kante edge (welche im Vektor ist) ein Gewicht hat, also edge-> weight.
Nun möchte ich meinen Vektor so sortieren, dass die Kante mit kleinstem Gewicht zuerst steht, etc.

Ich habe mal gegoogelt und habe etwas in der Art sort(vector.begin(), vector.end(),function comp) gefunden...ich verstehe aber nicht ganz wie ich das umsetzen kann. Könnte mir jemand erklären wie das funktioniert und wie ich meinen Vektor sortieren kann?

lieber Gruss & schon mal vielen Dank

SeppJ Moderator 22:34:44 15.05.2012 Titel:

Du schreibst eine Funktion die zwei const Edge* entgegen nimmt und true zurück gibt, wenn das erste im Sinne deiner Ordnung Argument kleiner ist als das zweite, ansonsten false. Und den Namen dieser Funktion übergibst du dann dem sort als dritten Parameter, die ersten beiden sind, wie in deinem Beispiel, der Anfang und das Ende des zu sortierenden Bereiches.

Bist du sicher, dass du einen vector benutzen möchtest und keinen Container, der automatisch ständig sortiert ist, wie z.B. (multi-)set? Edge klingt nach Grafikkram, da kenne ich mich nicht so aus, kann sein, dass ich Mist erzähle mit dem set und man das bei Computergrafik nicht so macht.

icarus2 Mitglied 22:37:04 15.05.2012 Titel:

Er will einen MST berechnen mit Kurskal. Hat in dem Fall nix mit Grafik zu tun.

So kannst du das machen:

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42	#include <algorithm> #include <iostream> #include <vector> using std::cout; using std::cin; using std::endl; using std::vector; struct Edge { // Other stuff double distance; Edge( double dist ) : distance(dist) {} }; // Compares two Edges by their distance bool compare( const Edge& e1, const Edge& e2 ) { return e1.distance < e2.distance; } int main() { vector<Edge> edges; edges.push_back( Edge(2.3) ); edges.push_back( Edge(0.3) ); edges.push_back( Edge(1.0) ); cout << "Unordered:" << endl; for ( size_t i = 0; i < edges.size(); ++i ) cout << edges[i].distance << endl; std::sort( edges.begin(), edges.end(), compare ); cout << endl << "Ordered:" << endl; for ( size_t i = 0; i < edges.size(); ++i ) cout << edges[i].distance << endl; }

Falls du etwas im Code nicht verstehst frage einfach nach

volkard Moderator 22:38:52 15.05.2012 Titel:

SeppJ schrieb:

Bist du sicher, dass du einen vector benutzen möchtest und keinen Container, der automatisch ständig sortiert ist, wie z.B. (multi-)set?

Ergänzend zu SeppJ möchte ich heap einwerfen.

ands Mitglied 22:44:30 15.05.2012 Titel:

Herzlichen Dank für die schnelle Antwort - genau das habe ich gesucht

volkard Moderator 22:50:06 15.05.2012 Titel:

Wenn Du statt der Funktion (genauer: des Zeigers auf die Funktion, aber das erledigt C++ automatisch) ein Comparator-Objekt übergibst, holst Du dann noch ein Quäntchen Performance heraus, weil dann sogar der dümmste Compiler inlinen kann.

Michael E. Mitglied 00:10:47 16.05.2012 Titel:

volkard schrieb:

Ergänzend zu SeppJ möchte ich heap einwerfen.

Ich staune gerade, dass die Seite von einer Uni sein soll. Bin ich so neben der Rolle? :eek:

Zuerst einmal ist der Algorithmus falsch formuliert. Man kann nicht einfach billigste Kanten in den Wald einfügen, bis er zusammenhängend ist. Dabei können Kreise entstehen, sodass das Ergebnis kein Baum ist. Dann sehe ich nicht, warum man alle Kanten in einem Heap vorhalten sollte. Ein sortiertes Array tuts ebenfalls. Die Laufzeit des Algorithmus wird mit dem Heap erklärt, aber auf die Laufzeit zum Vereinigen der Zusammenhangskomponenten im Wald geht er nicht ein. Der unten stehende Satz gilt nur, wenn alle Kantengewichte paarweise verschieden sind.

Edit: Auf der nächsten Seite wirds nicht besser. Da wird als Laufzeit von Prim O(m*log(n)) angegeben, was bei dichten Graphen schneller sein soll, weil bei Prim die Laufzeit m*log(m) = n²*log(n)*2 sei. Von Landaunotation hat der Herr wohl noch nichts gehört. Lustigerweise schreibt er zwei Sätze vorher, dass bei Prim jede Kante zweimal bearbeitet wird. Wo ist dieser Faktor 2 denn jetzt hin?

Sowas war mal ne Vorlesung?

Edit: Und bei negativen Kantenkosten ist das Kürzeste-Wege-Problem nicht wohldefiniert. Soso, auf konservativen Gewichten gibts also kein Bellman-Ford?

volkard Moderator 00:19:29 16.05.2012 Titel:

Michael E. schrieb:

volkard schrieb:

Ergänzend zu SeppJ möchte ich heap einwerfen.

Ich staune gerade, dass die Seite von eine Uni sein soll...

Ich muß gestehen, daß von der einfachen Heuristik "Graphentheorie => Heap" ausging. Die klappt verdammt oft. Einfach mal gegoogelt. Und dann habe ich einfach geglaubt, weil die Seite von einer Uni ist. Nein, habe ich nicht. Es paßte nicht. Der Algo forderte keinen Heap. Da war ich verwirrt. Und dann habe ich nachgedacht. Aber alles, was ich dachte, war widersprüchlich zur Uni-Seite. Nuja, Uni hat recht, dachte ich dann. Sorry.