quicksort will nicht so recht

[barton4]

Hi, ich versuche gerade eine Templateklasse zu schreiben die ein paar Sortieralgorithmen bereitstellt. Bisher habe ich selection, insert, bubble sort die alle funktionieren.
Leider komm ich beim quicksort nicht weiter :-(, entweder er sortiert es nicht richtig oder ich bekomme speicherzugriffsfehler usw.

template <class T> bool CSortAlgorithm<T>::QuickSort(T elements[], t_pos left, t_pos right)
{
	bool retval = true;
	
	if(left<right)
	{
		int il = left;
		int ir = right-1;
		while(true)
		{
			while(elements[il] < elements[right])il++;
			while(elements[ir] > elements[right] && il < ir )ir--;
			if(il>=ir)break;
			CSortAlgorithm<T>::swap(elements[il], elements[ir]);
		}

		CSortAlgorithm<T>::swap(elements[il], elements[right]);
		
		CSortAlgorithm<T>::QuickSort(elements, left, il-1);
		CSortAlgorithm<T>::QuickSort(elements, ir+1, right);
	}

	return retval;
}

weis jemand woran es liegt, ich hab quicksort jetzt schon x mal neugeschrieben ohne Erfolg.

[totycro]

Grundsätzlich ist es in so einem Fall meist hilfreich, wenn du dir den Programmablauf in einem Debugger ansiehst (unter Linux z.b. mit gdb), Speicherzugriffsfehler etwa kann man so sehr schnell lokalisieren und beheben.

Beim Durchsehen hab ich jetzt keinen Fehler bemerkt, es wäre hilfreich, wenn du so viel Quellcode postest, dass man es kompilieren kann (Stichwort Minimalbeispiel).

[BlueJay]

Genauso wichtig wäre das Testarray.

Bei meinen Versuchen (TurboPascal) mit Quicksort sind diese Teile so oft im Nirwana verschwunden (Stack overflow beim Stresstest), dass ich eine Shellsort-Variante bevorzuge.

so long,
BlueJay

[barton4]

hier mal der komplette code:

#include <iostream>
using namespace std;

template <class T> class CSortAlgorithm
{
public:
	typedef unsigned int t_length;
	typedef unsigned int t_pos;
	static void swap(T& a, T& b);
	static bool SelectionSort(T elements[], t_length length);
	static bool InsertSort(T elements[], t_length length);
	static bool BubbleSort(T elements[], t_length length);
	static bool QuickSort(T elements[], t_length length);
private:
	static bool QuickSort(T elements[], t_pos left, t_pos right);

};
//----------------------------------------------------------------------------------------|
//----------------------------------------------------------------------------------------\


template <class T> void CSortAlgorithm<T>::swap(T& a, T& b)
{
	T tmp = a;
	a = b;
	b = tmp;
}

template <class T> bool CSortAlgorithm<T>::SelectionSort(T elements[], t_length length)
{
	bool retval = true;

	t_pos minpos;
	for(t_pos i=0; i<length; i++)
	{
		minpos = i;
		for(t_pos k=i; k<length; k++)
		{
			if( elements[k] < elements[minpos] )
			{
				minpos = k;
			}
		}
		CSortAlgorithm<T>::swap(elements[i], elements[minpos]);
	}
	return retval;
}

template <class T> bool CSortAlgorithm<T>::InsertSort(T elements[], t_length length)
{
	bool retval = true;

	for(t_pos i=0; i<(length-1); i++)
	{
		for(signed long long k=i; k>=0; k--)	//wichitg!!! signed typ als Zaehlervarialble
		{
			if(k<0)break;						//geht doch ohne vorsortieren :-)
			if(elements[k]>elements[k+1])
			{
				CSortAlgorithm<T>::swap(elements[k], elements[k+1]);
			}
			
		}
	}
	
	return retval;
}

template <class T> bool CSortAlgorithm<T>::BubbleSort(T elements[], t_length length)
{
	bool retval = true;

	bool hasChanged=true;
	while(hasChanged)
	{
		hasChanged = false;
		for(t_pos i = 0; i<(length-1); i++)
		{
			if( elements[i] > elements[i+1] )
			{
				CSortAlgorithm<T>::swap(elements[i], elements[i+1]);
				hasChanged = true;
			}
		}
	}
	return retval;
}

template <class T> bool CSortAlgorithm<T>::QuickSort(T elements[], t_length lenght)
{
	bool retval = true;

	CSortAlgorithm<T>::QuickSort(elements, 0, lenght-1);
	
	return retval;
}

template <class T> bool CSortAlgorithm<T>::QuickSort(T elements[], t_pos left, t_pos right)
{
	bool retval = true;
	
	if(left<right)
	{
		T pivot = elements[right];
		t_pos il = left;
		t_pos ir = right-1;
		while(true)
		{
			while(elements[il] < pivot)il++;
			while(elements[ir] > pivot && il < ir )ir--;
			if(il>=ir)break;
			CSortAlgorithm<T>::swap(elements[il], elements[ir]);
		}
		CSortAlgorithm<T>::swap(elements[right], elements[ir]);
		CSortAlgorithm<T>::QuickSort(elements, left, il-1);
		CSortAlgorithm<T>::QuickSort(elements, ir+1, right);
	}

	return retval;
}

//----------------------------------------------------------------------------------------/
//----------------------------------------------------------------------------------------|

int main()
{
	int a[] = {5,1,3,9,6,5,7,2,10,11,4,};
	//int a[] = {5,1,3,1,3,6,45,23,54,55,52,9,6,5,7,2,10,11,4,};

	for( int i=0; i<(sizeof(a)/4); i++)
	{
		cout<<(sizeof(a)/4)<<"before sort: "<<a[i]<<endl;
	}

	CSortAlgorithm<int>::QuickSort(a, sizeof(a)/4);

	for( int i=0; i<(sizeof(a)/4); i++)
	{
		cout<<(sizeof(a)/4)<<"after sort: "<<a[i]<<endl;
	}

	cin.get();

	return 0;
}

[BLUESCREEN3D]

Und was hast du getan, um den Fehler zu finden?

Du kannst z.B. mit "g++ -g" kompilieren, dann "gdb a.out" aufrufen, anschließend einen Breakpoint setzen mit "break CSortAlgorithm<int>::QuickSort(int*, unsigned int, unsigned int)" und das Programm starten mit "run".
Es wird dann gleich wieder stoppen, weil QuickSort() aufgerufen wurde.
Von nun an willst du dir den Inhalt von "elements" anzeigen lassen: "display *elements@11" (das Array hat 11 Elemente, deshalb die 11).
Beim ersten Funktionsaufruf ist noch nichts zu sehen, also gibst du "continue" ein. Beim zweiten Aufruf ist auch noch alles in Ordnung, also nochmal "continue". Nun solltest du den Fehler sehen ...

Es sind übrigens zwei Fehler - der zweite wird sichtbar, sobald du den ersten behoben hast (Tipp: Überprüf den Wert von left und right).

[barton4]

ne richtig bekomm ich es nicht raus. Ein Fehler hab ich gefunden, nähmlich das left teilweise grösser war als right aber sonst nicht.

könntest du nicht einfach sagen worans liegt büütte


gruss martin

[BLUESCREEN3D]

Ein Fehler hab ich gefunden, nähmlich das left teilweise grösser war als right aber sonst nicht.

Das ist kein Problem.

Wenn du das mit dem Debugger noch nicht hinkriegst, kannst du dir den Inhalt des Arrays auch am Anfang der 2. QuickSort()-Methode ausgeben lassen, indem du so eine ähnliche Ausgabe, wie du sie schon in main() hast, einbaust.

Das sieht dann so aus:

{5, 1, 3, 9, 6, 5, 7, 2, 10, 11, 4} //erster Aufruf - alles unsortiert
{2, 1, 3, 4, 6, 5, 7, 5, 10, 11, 9} //zweiter Aufruf
{2, 3, 1, 4, 6, 5, 7, 5, 10, 11, 9} //dritter Aufruf

Was ist in der 3. Zeile falsch?

[barton4]

ok er hat die drei weiter nach links verschoben was natührlich gar nicht gewoltl ist.
Ich hab zwar die du es gesagt hast im gdb debuggt aber das array wurde in Hexadezimalen Zahlen dargestellt, die um einiges grösser waren als die Zahlen die ich ein meinem Array hatte, was ich etwas seltsam finde.

[WeenerChild]

aber das array wurde in Hexadezimalen Zahlen dargestellt, die um einiges grösser waren als die Zahlen die ich ein meinem Array hatte, was ich etwas seltsam finde.

Dir ist schon klar, dass ein array quasi nur ein konstanter pointer auf die Anfangsadresse des eigentlichen arrays ist, richtig?

[BLUESCREEN3D]

ok er hat die drei weiter nach links verschoben was natührlich gar nicht gewoltl ist.

Genau das ist der erste Fehler.
Versuch als nächstes rauszufinden, welche Zeile deines Quellcodes diesen Tausch vornimmt.
Dabei könnte dir in gdb der Befehl "step" helfen.

Ich hab zwar die du es gesagt hast im gdb debuggt aber das array wurde in Hexadezimalen Zahlen dargestellt, die um einiges grösser waren als die Zahlen die ich ein meinem Array hatte, was ich etwas seltsam finde.

Du hast das * vor elements vergessen:

display *elements@11

[barton4]

oh achso, ja ich wär es mal probieren.evt. nehm ich auch einen anderen quick sort ansatz.

[BLUESCREEN3D]

Also den Fehler zu finden sollte jetzt definitiv schneller gehen
Du hast es schließlich schon fast ...