3. Frage zum Quicksort

Frage zum Quicksort


  • 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!?

    0
  • B

    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!

    0
  • B

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

    0 

  • //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...

    0
  • B
     

    //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 😞

    0
  • M

    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.

    0
Anmelden zum Antworten