Quicksort-Problem

314159265358979

Quicksort auf verketteten Listen ergibt keinen Sinn.

krümelkacker

Auweia ... da ist eine ganze Menge falsch.

Das if (l<r) soll doch sicher if (l!=r) heißen; denn die Adressen der Knotenobjekte einer Liste sind nicht zwangsweise aufsteigend!

Part in QuickSort wird nie gesetzt, aber verwendet. Auch nicht durch den PreparePartition-Aufruf. Vielleicht möchtest Du ja den dritten Parameter per Referenz entgegen nehmen, also element*&p .

... bekomm ich zwei "linker-Fehler" und zwei warnungen, dass *temp und *part nicht initialisiert sind. Woran liegt das?

Bzgl Linker-Fehler: Wahrscheinlich hast du die ODR (one definition rule) verletzt.
Bzgl Warnungen: Uninitialisierte Variablen zu benutzen ist typischerweise ein Fehler. Deswegen ist der Compiler so nett, Dich davor zu warnen.

314159265358979 schrieb:

Quicksort auf verketteten Listen ergibt keinen Sinn.

Ich würde da auch lieber eine MergeSort Implementierung empfehlen, wo Elemente nie umkopiert, nur die Knoten neu verlinkt werden. Aber prinzipiell ist das mit dem QuickSort auch machbar mit 'nem average case von O(n*log(n)), falls ich mich gerade nicht völlig vertue. Zum Partitionieren sind nur BiDi-Iteratoren erforderlich.

vip*r

Danke für eure Hilfe!

Dass ich einen Quicksort nehmen soll, liegt in der Natur der Aufgabe und dafür kann ich nichts.

Hier die genauen Compiler-Fehler/Warnungen:

Fehler 2 error LNK1120: 1 nicht aufgelöste externe Verweise. C:\Users\ggg\Desktop\U5Aufgabe4_1\Debug\U5Aufgabe4_1.exe 1

Fehler 1 error LNK2019: Verweis auf nicht aufgelöstes externes Symbol ""public: void __thiscall list::Swap(class element *,class element *)" (?Swap@list@@QAEXPAVelement@@0@Z)" in Funktion ""public: void __thiscall list::PreparePartition(class element *,class element *,class element *)" (?PreparePartition@list@@QAEXPAVelement@@00@Z)". C:\Users\ggg\Desktop\U5Aufgabe4_1\U5Aufgabe4_1\list.obj

Edit: Mit was soll ich denn die zwei uninitialisierten pointer initialisieren?
Edit2: Nachdem ich jetzt die Referenz zum dirtten Aufruf in der PreparePartition-Methode hinzugefügt habe, sind die zwei Warnungen weg. Das Linker Problem besteht nach wie vor!

krümelkacker

auweia! Verstehst du denn auch, was du mit der Referenz gemacht hast?

Und wenn die Linkerfehler noch bestehen, hast Du noch immer ODR-Verletzungen im Code. Schau mal in Dein C++ Buch nach der ODR (one definition rule).

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?