BubbleSort

hi

ich habe eine Funktion für BubbleSort (absteigendes Sortieren)

void bubblesort(vector<pair_saving>& vps)
{
	//Diese Funktion führt eine absteigende Sortierung durch.

	for (unsigned int i=0; i<vps.size(); i++)
	{
		for (unsigned int j=vps.size()-1; j>i; j--)
		{
			if (vps[j].savings > vps[j-1].savings)
			{
				pair_saving tmp;
				tmp = vps[j];
				vps[j] = vps[j-1];
				vps[j-1] = tmp;
			}
		}
	}
}

das Problem ist das bei 300 Knoten die 2. For schleife schon 1 Mrd mal durchlaufen wird und deswegen der Zeitaufwand zu groß ist. Hat jemand einen Tip, wie ich die Sortierung schneller machen könnte ?

SeppJ

Hat jemand einen Tip, wie ich die Sortierung schneller machen könnte ?

Ganz einfach: Indem du nicht Bubblesort benutzt. Das ist eher eine Art Scherzsortierfunktion von Informatiklehrern, damit man da dran demonstrieren kann, wie man es nicht macht.

#include <algorithm>
#include <functional>

// ...

std::sort(daten.begin(), daten.end(), std::greater<datentyp>());

Vielen Dank. Hatte ich mir schon fast gedacht. Ich habe mir jetzt sort angeschaut. Wenn ich es richtig verstehe sortiert der die Werte dann aber aufsteigend ?

Fytch

ide schrieb:

Vielen Dank. Hatte ich mir schon fast gedacht. Ich habe mir jetzt sort angeschaut. Wenn ich es richtig verstehe sortiert der die Werte dann aber aufsteigend ?

gibt ja einen comparator den du selbst bestimmen kannst. (siehe seppj's code)

ich habe in dem Vector vps eine Structur verwendet:

struct pair_saving
{
	int o;
	int d;
	double savings;
};

und nach diesem savings wert soll sortiert werden. Kann es sein das es nicht funktioniert mit vps.savings.begin() etc. ?

Fytch

ide schrieb:

ich habe in dem Vector vps eine Structur verwendet:
struct pair_saving
{
	int o;
	int d;
	double savings;
};
und nach diesem savings wert soll sortiert werden. Kann es sein das es nicht funktioniert mit vps.savings.begin() etc. ?

überleg dir halt mal ob instanzen des types double wirklich eine methode "begin()". ich bezweifle es. vps hat jedoch sehr wohl eine solche. wie du das lösen kannst? schreib einen comparator der die member "savings" der vektor-einträge (bzw. der iterator-pointees) vergleicht. oder du bietest operatoren für deinen typen an und verwendest dann den naiven ansatz von seppj.

SeppJ

Doch, std::sort funktioniert mit allem. Du musst bloß eine passende Vergleichsfunktion angeben. Zum Beispiel so:

bool comp_pair_saving_greater (const pair_saving& lhs, const pair_saving& rhs) 
{
  return lhs.savings > rhs.savings;
}

// ...

std::vector<pair_saving> data;

// ...

std::sort(data.begin(), data.end(), comp_pair_saving_greater);

Oder

bool operator>(const pair_saving& lhs, const pair_saving& rhs) 
{
  return lhs.savings > rhs.savings;
}

// ...

std::sort(data.begin(), data.end(), std::greater<pair_saving>());

Oder

std::sort(data.begin(), data.end(), [](const pair_saving& lhs, const pair_saving& rhs) { return lhs.savings > rhs.savings;});

(Alle ungetestet, mögliche Tipp-/Syntaxfehler dienen der Übung des Lesers )

vielen vielen dank.

Ich werde mich morgen mal dran versuchen