Quicksort-Problem

Caligulaminus

Der Linkerfehler rührt wohl daher, daß dir in der ersten Zeile ein list:: fehlt.

vip*r

Tatsächlich, der linker-Fehler kommt in der Tat von dem vergessenen list::. Danke!

Also hab ich wohl die ODR-Regel nicht verletzt.

Was ich mit *& gemacht habe, verstehe ich in der Tat nicht so genau. Ich kenne den &-Operator bei Zeigern als einen Operator, der mir die Adresse von einem Zeiger ausgibt.
Ich hab hier jetzt in meinem C++Buch auch nachgelesen, aber über die Kombination von * mit & in einem Funktionsaufruf leider nichts gefunden...

Nachdem der linker Fehler jetzt weg ist, bekomm ich eine exception, wegen der nicht initialisierten *temp Variable. Sie mit einem Wert für val zu initialisieren hilft auch nichts

vip*r

icarus2 schrieb:

Das Problem mit den Warnungen liegt hier:
void Swap(element *a, element *b) 
{ 
    element *temp; // Uninitialisierter Zeiger

    temp->val = b->val; // Hier knallts deswegen
    b->val = a->val; 
    a->val = temp->val; 
}
und dann hast du noch einen solchen in Zeile 12. Die sollte man halt irgendwie initialisieren.

Die Warnungen provozieren dann im weiteren Verlauf des Quicksorts auch den Absturz. Ich hab nun versucht, die pointer so zu initialisieren, was aber auch nicht geht:

void list::Swap(element* a, element* b)
{
	element* temp;

	temp->next = NULL;
	temp->prev = NULL;
	temp->val = 0;

	temp->val = b->val;
	b->val = a->val;
	a->val = temp->val;
}

Wie macht man das jetzt richtig?

Jester

314159265358979 schrieb:

Quicksort auf verketteten Listen ergibt keinen Sinn.

Warum? Oder besser: seit wann?

krümelkacker

vip@r schrieb:

Also hab ich wohl die ODR-Regel nicht verletzt.

Naja, dir fehlte eine Definition von etwas, was Du nutzen wolltest.

vip@r schrieb:

Was ich mit *& gemacht habe, verstehe ich in der Tat nicht so genau. Ich kenne den &-Operator bei Zeigern als einen Operator, der mir die Adresse von einem Zeiger ausgibt.
Ich hab hier jetzt in meinem C++Buch auch nachgelesen, aber über die Kombination von * mit & in einem Funktionsaufruf leider nichts gefunden...

Da ist auch nichts besonderes an der Kombination.
* deklariert einen Zeiger und
& deklariert eine Referenz.

vip*r

krümelkacker schrieb:

Naja, dir fehlte eine Definition von etwas, was Du nutzen wolltest.

Was wollte ich denn nutzen? So wie ich das von icarus2 verstanden habe, knallts in meinem Programm weil ich eben diese zwei Zeiger nicht initialisiert habe. Wie initialisiere ich denn nun diese Zeiger? So wie ich es versucht habe, funktioniert es jedenfalls nicht...

Jester

Schreib einfach

element temp;

temp.val=...

Dann liegt das temporäre element auf dem stack und zumindest der teil passt dann.

vip*r

Gut, da hätt ich auch drauf kommen können...

Wie mach ich das dann weiter beim part? Ich hab das hier auch mal als element part; deklariert, aber dann passt der rekursive Aufruf von Quicksort() nicht mehr, da ich von der main aus mit einem element* aufrufe, beim rekursiven Aufruf aber mit einem part.prev...

DocShoe

Jester schrieb:

314159265358979 schrieb:

Quicksort auf verketteten Listen ergibt keinen Sinn.

Warum? Oder besser: seit wann?

Warum:
Weil Quicksort wahlfreien Zugriff auf Elemente benutzt, z.B. bei der Bestimmung des Pivot Elementes und der Partitionierung. Man kann das natürlich auch für einfach und doppelt verkettete Liste implementieren, aber dann wird´s erbärmlich langsam. Für verkettete Listen ist Mergesort die bessere Alternative.

Seit wann:
Schon immer, prinzipbedingt.

Jester

DocShoe schrieb:

Jester schrieb:

314159265358979 schrieb:

Quicksort auf verketteten Listen ergibt keinen Sinn.

Warum? Oder besser: seit wann?

Warum:
Weil Quicksort wahlfreien Zugriff auf Elemente benutzt, z.B. bei der Bestimmung des Pivot Elementes und der Partitionierung.

Bei der Partitionierung jawohl schonmal nicht, man läuft von beiden Enden los und vertauscht die Elemente, wenn das linke größer als das Pivot ist und das rechte größer. Wozu braucht man da nen wahlfreien Zugriff? Das Pivot-Element ist ne andere Sache, aber man kann ja wie hier vorgeschlagen immer das erste nehmen, oder sich eben beim vorherigen Partitionierungsschritt schon das Pivot-Element mit rausfriemeln ohne mehr Laufzeit zu brauchen.

Magst Du's nochmal versuchen?