C++ Suche quicksort Algorithmus

[lordfritte]

Hallo ich bin auf der Suche nach dem quicksort Algorithmus, leider habe ich bisher nicht wirklich was gefunden was ich so einigermaßen verstehe.
Bis her habe ich nur das Gefunden, aber der Algorithmus scheint ziemlich lahm zu sein, ab 1000 Elementen braucht er schon über eine Sekunde und 2. scheint dieser Algorithmus auch ziemlich instabil zu sein, es komm sehr oft vor dass es zu einem negativen Index kommt und dann schmiert natürlich alles ab.

 

[Tumbleweed]

Was willst du denn sortieren?

Quicksort kannst du dir doch selbst bauen, wenn du das Prinzip verstanden hast. Quicksort ist für kleine Mengen von Elementen eher weniger gut geeignet.

 

[lordfritte]

Ich schreibe mir zur zeit eine Klasse für eine verkettet Liste, diese würde ich auch gerne Sortieren.
Mit dem qsort was in C vorhanden ist gute Erfahrungen gemacht habe würde ich dann gerne qsort nutzen, aber das aus C kann ich leider nicht nutzen deswegen muss/möchte ich selber eins schreiben.

EDIT: Es könnte aber auch an meine Swap Funktion liegen, für einen Austausch zweier Elemente benötigt diese 0.000115 Sekunden * 5000 Elemente = 0.575 Sekunden, aber trotzdem möchte ich die Instabilität vermeiden.

 

[Tumbleweed]

Also wie gesagt, wenn du wenige Elemente hast (1000 ist auch noch nicht viel), dann würde ich einen anderen Algorithmus nehmen. Ansonsten kannst du ja deinen bisherigen Quicksortversuch mal posten. Ich steck zwar in C++ nicht so drin und habe auch die Sortieralgorithmen verdrängt, aber da findet sich schon wer, der dir sagt woran es liegt.
Kann durchaus auch daran liegen, dass Quicksort für deine kleine Zahl von Elementen nicht lohnt. Sind die 5000 Elemente denn immer gleich und auch immer gleich sortiert bevor dein Quicksort durchläuft?

 

[lordfritte]

Das ist ein bisschen größerer Code, dazu kommt dass ich in der Klasse eine template nutze.
Also hier mal der wichtige Code:

//Sort:
template<typename T>
void MyList<T>::Sort(MyListUtilities<T> *comparer)
{
	this->List_QSort(comparer, 0, this->_iCount - 1);
}

//QSort:
template<typename T>
void MyList<T>::QSort(MyListUtilities<T> *comparer, int l, int r)
{
	int i, j;
	T median;

	if(r > l)
	{
		median = this->GetValue(r);
		i = l-1;
		j = r;

		for(;;)
		{
			while(comparer->Compare(this->GetValue(++i), median) < 0);
			while(comparer->Compare(this->GetValue(--j), median) > 0);

			if(i >= j)
				break;

			this->Swap(i, j);
		}

		this->Swap(r, i);

		this->QSort(comparer, l, i-1);
		this->QSort(comparer, i+1, r);  
	}
}

GetValue gibt mir den T Wert zurück(bei T = int ist das ein int, bei T = float ist das ein float, etc.)
Swap tauscht 2 T elemente
MyListUtilities<T> *comparer enthält nur eine Compare Funktion, übergabe T a, T b rückgabe int(0, > 0, < 0)

Die 5000 Elemente sind immer anders, zum testen fülle ich die Liste mit zufälligen int werten.

 

[Raechaer]

Quicksort ist für eine verkettete Liste wegen des benötigten random access denkbar ungeeignet (weil du für jeden Zugriff zum richtigen Element iterieren musst), besser wäre wohl Merge sort.

Und da dein Swap nur mit Indizes arbeitet wird da wohl auch nochmal über die Liste iteriert was nochmals Zeit kostet.

 

[Ernie123]

Da hab ich in DuA wohl gepennt...
(Datenstrukturen und Algorithmen)

 

[IceMatrix]

warum nutzt du nicht einfach die CRT-prozedur qsort() ?
die ist hoch optimiert und mit ziemlicher wahrscheinlichkeit deinen eigenimplementierungen weit überlegen.

 

[lordfritte]

warum nutzt du nicht einfach die CRT-prozedur qsort() ?
die ist hoch optimiert und mit ziemlicher wahrscheinlichkeit deinen eigenimplementierungen weit überlegen.

Wie soll denn das gehen? Ich kann doch nicht einfach 2 Elemente vertauschen? Ich muss doch die Adressen ändern, jedes Element in der Liste hat einen Zeiger auf das nächste und auf das vorige Element.

Quicksort ist für eine verkettete Liste wegen des benötigten random access denkbar ungeeignet (weil du für jeden Zugriff zum richtigen Element iterieren musst), besser wäre wohl Merge sort.

Und da dein Swap nur mit Indizes arbeitet wird da wohl auch nochmal über die Liste iteriert was nochmals Zeit kostet.

Ich habe mir Merge Sort mal angesehen, gibt es nichts ohne Hilfsarray? Sonst muss ich ja wieder riesige Mengen speicher anlegen.

 

[Raechaer]

Merge Sort funktioniert auf verketteten Listen ohne Hilfsarray. Eine kurze Google Suche führt dich auf http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html, dort wird der Algorithmus erklärt und es gibt sogar C Code.

Edit: Abhängig von der Länge der Liste bist du aber unter Umständen mit einem simplen Selection Sort schneller. Wenn es wirklich auf Geschwindigkeit ankommt hilft wohl nur ein bisschen Benchmarking und eine Fallunterscheidung.

 

[lordfritte]

Quicksort ist für eine verkettete Liste wegen des benötigten random access denkbar ungeeignet (weil du für jeden Zugriff zum richtigen Element iterieren musst), besser wäre wohl Merge sort.

Und da dein Swap nur mit Indizes arbeitet wird da wohl auch nochmal über die Liste iteriert was nochmals Zeit kostet.

Merge Sort funktioniert auf verketteten Listen ohne Hilfsarray. Eine kurze Google Suche führt dich auf http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html, dort wird der Algorithmus erklärt und es gibt sogar C Code.

Edit: Abhängig von der Länge der Liste bist du aber unter Umständen mit einem simplen Selection Sort schneller. Wenn es wirklich auf Geschwindigkeit ankommt hilft wohl nur ein bisschen Benchmarking und eine Fallunterscheidung.

Danke, also ich bin gerade schon am Benchen, die Zugriffszeit konnte ich schon enorm von durchschnittlich bei 1000 zufälligen Zugriffen von 0.000027 auf 0.000015 Sec's verringert.

 

[lordfritte]

Also ich habe ein neues dickes Problem, ich habe bei meiner verketteten Liste den Zugriffoperator überschrieben um auch so: myList[3]; auf die Elemente zugreifen zu können.
Hier:

template<typename T>
T& MyList<T>::operator[](int index)
{
	return this->GetValue(index);
}

template<typename T>
T& MyList<T>::GetValue(int index)
{
	Node* current = NULL;
	int x = 0;
	int m = this->_iCount / 2;

	if(index < 0)
		throw "Der Index darf nicht negativ sein.";
	else if(index >= this->_iCount)
		throw "Der Index lag ausserhalb des gueltigen Bereichs.";
	else
	{
		if(index <= m)
		{
			current = this->_first;
			while(x < index)
			{
				current = current->next;
				x++;
			}
		}
		else
		{
			x = this->_iCount - 1;
			current = this->_last;
			while(x > index)
			{
				current = current->prevouis;
				x--;
			}
		}
		
		return current->value;
	}
}

Also normales Objekt geht es wunderbar, aber wenn ich meine Liste als Zeiger habe kommt da nur Datenmist zurück.
Aber mit myList.GetValue(x);/myList->GetValue(x); geht es immer

 

[Raechaer]

Der Fehler liegt vermutlich nicht im geposteten Code (und übrigens sollten die beiden Methoden const sein).

Davon abgesehen macht meiner Meinung nach operator[] bei einer verketteten Liste keinen Sinn (aus den gleichen Gründen wie quicksort), wenn du random access willst nimm ein Array.

 

[lordfritte]

Aber wenn ich einen Array nehme, dann brauche ich ja den ganzen Mis.. nichts...
Aber warum sollte der operator[] keinen sinn machen? Ich möchte doch so: list[x] drauf zugreifen..

 

[Raechaer]

Operator[] ergibt keinen Sinn weil er auf einer verketteten Liste in O(n) ist und somit die Vorteile einer Liste gegenüber einem Array wieder zunichte macht. Der Zugriff auf die Elemente einer Liste ist hauptsächlich per Iterator sinnvoll weil du damit dann auf alle Elemente in O(n) zugreifen kannst (und nicht O(n^2) wie mit Operator[]).

Und wenn du tatsächlich random access benötigst und nicht nur über alle Elemente iterieren willst ist eine Liste numal denkbar ungeeignet, für sowas verwendet man dynamisch wachsende Arrays (die erst beim Einfügen von sehr vielen Elementen tatsächlich langsamer werden als Listen).

 

[lordfritte]

Aber ist der Vorteil einer Liste nicht dass ich eben nicht mehr zusammanhängenden Speicher habe?
Aber naja, mit GetValue gehts ja auch.


Ich könnte ja auch das List aus C++ nehmen, aber was mich daran stört das ich nicht versteh nach welchem Prinzip die Methode Sort() funktioniert und arbeitet.
Jetzt gibt es natürlich auch merge aber ich hätte gerne zum Vergleich keine Methode sondern eine Klasse.
Das habe ich bei .NET entdeckt und finde diese Lösung super, klar man braucht mehr Code aber durch den Konstruktor hat man eben den Vorteil dass man nicht nur Objekt A und Objekt B in den Vergleich einfließen lassen kann, sondern auch zusätzliche Parameter.
z.b. wie soll er sortieren aufwärts oder abwärts und wonach soll er sortieren.

 

[Raechaer]

Der Vorteil einer Liste ist, dass du sehr schnell (nämlich in konstanter Zeit) Elemente hinzufügen und entfernen kannst. Der Nachteil ist aber, dass du auf die Elemente nur in O(n) zugreifen kannst.

Bei einem dynamischen Array ist's (vereinfacht gesagt) gerade andersherum, aber da ein Array weniger Speicheroverhead hat (du brauchst keine next und prev Zeiger), deutlich einfacher (und schneller) zu Implementieren ist und im Normalfall öfters auf Elemente zugegriffen wird als dass Elemente hinzugefügt werden ist in solchen Fällen das Array der bessere Datentyp.

Oder anders gesagt, wer auf die Elemente einer Liste mit operator[] zugreift arbeitet höchst wahrscheinlich mit dem falschen Datentyp

 

[lordfritte]

was ich nur nicht verstehe ist das:
Liste als normales Objekt, T& operator[] geht super, T& GetValue() Methode geht super.
Liste als zeigerObjekt, T& operator[] geht garnicht, T& GetValue() Methode geht super.

Dabei greift der operator[] ja auf GetValue() zu.

 

[Raechaer]

Ich könnte ja auch das List aus C++ nehmen, aber was mich daran stört das ich nicht versteh nach welchem Prinzip die Methode Sort() funktioniert und arbeitet.
Jetzt gibt es natürlich auch merge aber ich hätte gerne zum Vergleich keine Methode sondern eine Klasse.

Meinst du sowas:

#include <list>
#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

struct comp : public std::binary_function<int, int, bool>
{
	comp(bool ascending)
		: ascending(ascending)	{};
	bool operator()(const int& left, const int& right) const
	{
		if (ascending)
			return left < right;
		else
			return right < left;
	}
private:
	bool ascending;
};

int main()
{
	list<int> l;
	// generate list with 10 random numbers
	generate_n(front_inserter(l), 10, rand);
	cout << "Before sorting:" << endl;
	copy(l.begin(), l.end(), ostream_iterator<int>(cout, " "));

	// sort ascending
	l.sort(comp(true));
	cout << "\nAfter sorting:" << endl;
	copy(l.begin(), l.end(), ostream_iterator<int>(cout, " "));

	// sort descending
	l.sort(comp(false));
	cout << "\nAfter sorting:" << endl;
	copy(l.begin(), l.end(), ostream_iterator<int>(cout, " "));	
}

Vielleicht solltest du dir aber erstmal überlegen ob du wirklich eine Liste willst oder ob du nicht mit vector viel besser bedient bist.

 

[lordfritte]

Sieht interessant aus, danke.