Frage zum Quicksort

bandchef

Hi Luete!

Wie ihr unten seht, hab ich eine korrekte Implementierung eines Teils des Quicksort-Algos. Ich hab in meiner main eine Folge von 10 willkürlichen Zahlen angegeben, die ich nun mit diesem Algo sortieren lassen möchte. Meine Aufgabe ist es nun, das Pivotelement (oder Trennelement) zufällig auszuwählen und nicht in Abhängigkeit von "f" (first, erstes Element in der Zahlenfolge) zu wählen.
Damit dies nun zufällig funktioniert, hab ich mir in der main einen random seed gesetzt den ich modulo 9 (für Zahlen von 0 bis 9) und rufe diesen in der 4. Zeile des Codes unten als Adressierung des Arrays auf.
Ich hab nun gedacht, dass dies schon alles war, leider sortiert er mir jetzt nicht mehr richtig und ich sehe nicht so wirklich, was da nun fehlt

Ich weiß, dass dies so zu keiner effizienten Implementierung führen wird; ist mir aber egal, da es eine Übung sein soll!

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

Damit dies nun zufällig funktioniert, hab ich mir in der main einen random seed gesetzt den ich modulo 9 (für Zahlen von 0 bis 9)

Wieso 0 bis 9? Wieso nicht ein Wert aus der zu sortierenden Menge?

Denk nochmal ganz gründlich nach, wie Quicksort funktioniert und welche Bedeutung das Pivot hat.

bandchef

Ich wähle ja mit dem rand() und modulo nur die Adressierung aus die auf Grund des beschränkten Arrays von 10 Elementen (also 0 bis 9) so dann den echten Wert aus der "zufällig" ausgewählten Stelle der Pivot-Variabel zuweist.

Was ist da jetzt falsch an meiner Überlegung?

bandchef

Ahhhh!

Jetzt glaub ich weiß ich worauf du hinaus wolltest! Da ich 10 Werte habe, und der Quicksort ja ein Divide&Conquer Algo ist, darf ich als Adressierung nur die Hälfte, also von 0 bis 5 wählen! Richtig?

SeppJ

bandchef schrieb:

Was ist da jetzt falsch an meiner Überlegung?

Na, die 0 bis 9, wie ich schon sagte. Guck dir nochmal an, wie Quicksort funktioniert. Das bringt schließlich nichts, wenn ich dir jetzt einfach die Lösung sage. Schreib auch mal zu allen deinen einbuchstabigen Variablennamen genau auf, was sie bedeuten.

bandchef schrieb:

Jetzt glaub ich weiß ich worauf du hinaus wolltest! Da ich 10 Werte habe, und der Quicksort ja ein Divide&Conquer Algo ist

JA! Und daraus folgt?

, darf ich als Adressierung nur die Hälfte, also von 0 bis 5 wählen! Richtig?

Das hätte ich jetzt nicht als Folgerung erwartet.

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

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?