Frage zum Quicksort

[bandchef]

Ich glaub da hat sich jetzt was überschnitten...

Leider funktioniert meine Idee so auch nicht. Hier nochmal der Code:

void PreparePartition(int a[], int f, int l, int &p)
{
	//Pivot-Element
	int pivot = a[(rand() % 5)];
	//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]);
}

[SeppJ]

bandchef schrieb:

Ich glaub da hat sich jetzt was überschnitten...

Habe oben noch eine Antwort reineditiert.

[bandchef]

Hast du schon einmal einem Baby zugesehen, das Laufen lernt? Erst sieht alles richtig aus und dann fällt es voll auf die Fresse

Das hier empfinde ich grad als Frechheit. Ich teile leider keinen Nerd-Humor. Aber gut. Wenn du der Meinung bist. Deine Aussage soll jetzt von meiner Seite aus der Zusammenarbeit keinen Abbruch tun.

Meine Aussage ist also richtig, dass das ein Divide&Conquer Algo ist. So ein Algo teil sich immer weiter auf, bis die Element elementar werden und quasi "sortiert" sind.

Ich erwarte jetzt keine Lösung der Aufgabe sondern, würde ich dich nun bitten, etwas gezielter nach zu helfen? Hat also rand()%9 doch gestimmt?

[SeppJ]

bandchef schrieb:

Ich erwarte jetzt keine Lösung der Aufgabe sondern, würde ich dich nun bitten, etwas gezielter nach zu helfen?

Was soll ich denn sonst noch sagen? Du musst schon mitdenken. Zum Beispiel hast du

Schreib auch mal zu allen deinen einbuchstabigen Variablennamen genau auf, was sie bedeuten.

nicht gemacht, obwohl du deinen eigenen Code anscheinend nicht verstehst.

Wie kommst du von

So ein Algo teil sich immer weiter auf, bis die Element elementar werden und quasi "sortiert" sind.

auf 9 oder 5?

Hat also rand()%9 doch gestimmt?

Ja, bestimmt. Schließlich war es nur mein allererster Hinweis, was nicht stimmt.

[bandchef]

Entschuldige Bitte. Die Aufgabe hab ich überlesen in meinem Eifer.

f = first element, l = last element, a[] = Zahlenfolge, p = Part, pivot sollte klar sein.

swap() ist eine Funktion die die Elemente durchtauscht.

Naja pro rekursivem Aufruf wird's eben immer kleiner. 10 wird in der Mitte geteilt, dann hat man zwei rays à 5 Elemente. Dann werden die zwei aufgeteilt. In bspw. 2 und 3 usw usf.

Ich hab mir nun nochmal Ggedanken gemacht:

void PreparePartition(int a[], int f, int l, int &p)
{
	//Pivot-Element
	int index = f + rand() % (l-f+1);
	int pivot = a[index];
	//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]);
}

[SeppJ]

bandchef schrieb:

Naja pro rekursivem Aufruf wird's eben immer kleiner. 10 wird in der Mitte geteilt, dann hat man zwei rays à 5 Elemente. Dann werden die zwei aufgeteilt. In bspw. 2 und 3 usw usf.

Fast. Der genaue Algorithmus stimmt zwar nicht (guck dir doch bitte nochmal die Rolle des Pivot an!), aber wir stellen schon einmal fest, der Bereich wird immer kleiner. Mit dieser Beschreibung und meinen vorherigen Hinweisen, dass dies irgendwie mit der Wahl der Pivots zu tun haben könnte, was schlussfolgerst du nun daraus?

[Th69]

Naja pro rekursivem Aufruf wird's eben immer kleiner. 10 wird in der Mitte geteilt, dann hat man zwei rays à 5 Elemente. Dann werden die zwei aufgeteilt. In bspw. 2 und 3 usw usf.

Denkfehler!

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).

[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