Frage zum Quicksort

bandchef

Dass ich die Modulorechnung pro rekursivem Aufruf irgendwie anpassen müsste. Im ersten Aufruf tut's %5. Im zweiten kann ich mich dann entscheiden ob %3 oder %4.

Richtig oder auch wieder vorbei?

Hab grad noch einen Code editiert...

SeppJ

bandchef schrieb:

Im zweiten kann ich mich dann entscheiden ob %3 oder %4.

Wie viele Elemente hast du denn zu sortieren?

Sepp, vllt. solltest du deinen Beitrag noch mal editieren, denn das "Genau" stimmt eben nicht (ok, der erste Satz von bandchef stimmt, aber die beiden anderen nicht).

Gemacht. Ich war schon glücklich, dass überhaupt erkannt wurde, dass der Algorithmus rekursiv auf immer weniger Daten arbeitet.

bandchef

Wie viele Elemente hast du denn zu sortieren?

Ich hab 10 Werte zu sortieren!

SeppJ

bandchef schrieb:

Wie viele Elemente hast du denn zu sortieren?

Ich hab 10 Werte zu sortieren!

Tut mir leid, ich geb's auf.

bandchef

Na dann! Dankeschön!

bandchef

Das war eine rhetorische Antwort. Kann man mir nicht trotzdem weiter helfen?

Th69

Wie viele Werte hast du pro Aufruf deiner PreparePartition()-Funktion zu sortieren? Tipp: Parameter beachten.

bandchef

Ich gehe mal davon aus, dass du die beiden Parameter f und l meinst, oder? f=0 und l=9. Ich hab mir noch weiter Gedanken gemacht und dabei darauf gestoßen, dass ich wohl, dass als Index verwendete f gleich dem rand() % 9 setzen sollte. Das sieht dann so aus:

void PreparePartition(int a[], int f, int l, int &p)
{
	//Pivot-Element
	//f = f + rand() % (l-f+1);
	int f = rand() % 9;
	int pivot = a[f];
	//int pivot = a[f];
	p = f-1;

	for(int i = f; i <= l; i++)
	{
		if(a[i] <= pivot)
		{
			p++;
			swap(a[i], a[p]);
		}
	}

	//Pivot an die richtige Stelle
	swap(a[f], a[p]);
}

Komischerweise geht das dann noch immer nicht. Was ich auch nicht so ganz verstehe, ist, dass wenn ich das Programm ein paar Mal hintereinander starte, die Sortierung immer wieder mal sporadisch funktioniert! Ich gehe mal davon aus, dass das zufälligen Zahlen geschuldet ist. Immer wenn die Random-Funktion 0 berechnet ist es ja der Wert mit dem der Algorithmus standardmäßig funktioniert.

Das Problem welches ich damit noch immer hab, löst es aber leider trotzdem nicht.

Edit:

Die Funktion drunter ist die rekursiv aufrufende Funktion:

void Quicksort(int a[], int f, int l)
{
	int part;
	if(f < l)
	{
		PreparePartition(a,f,l,part);
		Quicksort(a,f,part-1);
		Quicksort(a,part+1,l);
	}
}

Kann es sein, dass die ganze Sache nicht funktioniert, weil ich das f mit den Randomzahlen vor dem rekursiven Aufruf berechnen lassen muss?

Th69

So, ich bin's jetzt Leid - hier die Lösung:

void PreparePartition(int a[], int f, int l, int &p)
{
    //Pivot-Element
    int range = l - f + 1;
    int rnd = rand() % range;
    int pivot = a[f+rnd];

    // ...
}

Ich hoffe, du verstehst es wenigstens!?

bandchef

Danke! Jetzt weiß ich was ich bei meinem Beispiel vor ein paar Einträgen falsch gemacht habe. Ich habe einen änlichen Ansatz mal hier vorgestellt aber nicht erkannt, dass ich die Modulo-Rechnung in Abhängigkeit last und first Element machen muss!

Danke!

bandchef

Ich muss leider enttäuschen. Ich hab zwar so wie du gedacht, dass es so funtionieren könnte, aber es tut's leider nicht. Ich hab das jetzt in meiner Implementierung ausprobiert, aber es funktioniert nicht. Ich werde jetzt mal alles posten:

void swap(int &a, int &b)
{
	int h = b;
	b = a;
	a = h;
}

void PreparePartition(int a[], int f, int l, int &p)
{
	//Pivot-Element
	int range = l - f + 1;
	int rnd = rand() % range;
	int pivot = a[f + rnd];
	p = f-1;

	for(int i = f; i <= l; i++)
	{
		if(a[i] <= pivot)
		{
			p++;
			swap(a[i], a[p]);
		}
	}

	//Pivot an die richtige Stelle
	swap(a[f], a[p]);
}

void Quicksort(int a[], int f, int l)
{
	int part;

	if(f < l)
	{
		PreparePartition(a,f,l,part);
		Quicksort(a,f,part-1);
		Quicksort(a,part+1,l);
	}
}

Aufrufen tu ich die Funktion Quicksort() aus der main mit l=9 und f=0 soweit einem 10-elementige int-Array...

Th69

//Pivot an die richtige Stelle
swap(a[f], a[p]);

Siehst du es?

Edit: am besten, du führst es im Debugger Schritt für Schritt durch...

bandchef

//Pivot an die richtige Stelle
swap(a[f+rnd], a[p]);

Wenn ich nun den Code so abwandle geht's noch immer nicht. Ich hab nun einige Rekursionen durchkompiliert aber ich finde den Fehler nicht. Langsam ist's auch bei mir mit der Geduld vorbei

minastaros

bandchef schrieb:

[...] aber ich finde den Fehler nicht. Langsam ist's auch bei mir mit der Geduld vorbei

Ganz schlechte Ausgangsposition, wenn man programmieren will... Wenn's mit Probieren nicht klappt (meistens nicht), dann nur mit Untersuchen. Genau das wurde Dir ja schon mehrfach gesagt. Also:

Du hast ja ein 10-stelliges Test-Array mit (hoffentlich) fixen Test-Daten. Das ist noch übersichtlich.

Male das Ganze doch mal auf ein Blatt Papier mit den selben Werten auf und simuliere dann Schritt für Schritt von Hand, was das Programm tun sollte. Dann gehst Du mit dem Debugger her und führst es am Rechner Schritt für Schritt aus, beobachtest die Variablen und schaust, was es tatsächlich tut. Irgendwo zeigt sich, ob der Fehler im Design oder in der Implementierung liegt.

Ähnlich wie die hier: http://de.wikipedia.org/wiki/Quicksort#Beispiel_teile.28links.2C_rechts.29

Ohne Deinen Code jetzt in Gänze zu durchdenken, fällt mir auf den ersten Blick etwas auf:

bandchef schrieb:

void PreparePartition(int a[], int f, int l, int &p)
{
    /* ... */
	int pivot = a[f + rnd];
	p = f-1;

	for(int i = f; i <= l; i++)
	{
		if(a[i] <= pivot)
		{
			p++;
			swap(a[i], a[p]);

Wenn PreparePartition() mit f=0 aufgerufen wird und das Element a[0] kleiner oder gleich das Pivot-Element ist, was macht dann das swap? Irgendwie seltsam überflüssig, oder nicht? Zumindest nicht der performanteste Ansatz und ziemlich sicher (wie gesagt, ich hab's nicht komplett durchdacht) ein Hinweis auf einen Fehler.