Quick Sort - bin ich zu blöd?

[Guest]

Hey Leute... also nachdem ich jetzt schon seit über einer Woche dran sitze und den Fehler suche hab ich mich entschlosse das ganze mal hier zu posten...
Also ich habe den QuickSort - Algorithmus von Wikipedia in Java umgesetzt (also den Pseudocode)
Siehe: http://de.wikipedia.org/wiki/Quicksort
Eigentlich war dabei kein Problem... den Algorithmus an sich habe ich verstanden und auch sonst war eigentilch alles easy
Natürlich wollte ich das ganze auch testen und habe gleich ein Programm dazu geschrieben... im Average-Case (also wenn das Feld zufällige Zahlen beinhaltet) klappt alles super... die Zahlen werden richtig sortiert und alles ist bestens...

Das Problem taucht jetzt komischerweise beim Best-Case auf (wenn alle Zahlen in der richtigen Reihenfolge sind...)
Ich kann das Feld mit den Zahlen nicht größer als 10000 machen, da mir Java ansonsten die Fehlermeldung:

Exception in thread "main" java.lang.StackOverflowError

ausgibt... ich bin echt am verzweifeln, das macht er nämlich nur beim Best-Case... ich häng mal mein Code an...

Die Methode QuickSort...

	public static int[] QuickSort (int daten[],int links,int rechts) {
		if (links < rechts) {
			int teiler = teile (daten,links,rechts);
			QuickSort (daten,links,teiler-1);
			QuickSort (daten,teiler+1,rechts);
		}
		return daten;
	} //QuickSort

Die Methode teile

	private static int teile (int daten[],int links,int rechts) {
		int i = links;
		int j = rechts-1;
		int pivot = daten[rechts];
		
		while (i < j) {
			while ((daten[i]<=pivot) && (i<rechts)) 
				i++;
			
				
			while ((pivot<=daten[j])&& (j>links)) 
				j--;
				
			if (i<j) 
				Swap (daten,i,j);	
		}
		if (daten[i]>pivot)
			Swap (daten,i,rechts);
		return i;
	}

Die Methode Swap vertauscht zwei Felder miteinander

	private static int[] Swap (int daten[], int eins, int zwei) {
		
		int hilfe=daten[eins];
		daten[eins] = daten[zwei];
		daten[zwei] = hilfe;
		return daten;
	}

Aus der Main-Methode wird QuickSort aufgerufen... hier zwei Auszüge aus meiner Main-Methode, die die Feldbelegung verdeutlichen, sowie den Aufruf der Methode QuickSort

		int[] feld; 
		feld = new int[10000];
		for (int i=0;i<=feld.length-1;i++)
			feld[i]=i;
		feld = QuickSort(feld,0,feld.length-1);

Hat irgendwer eine Ahnung wo sich der Fehler versteckt hat?! Ich wär demjenigen echt so dermaßen dankbar...

 

[tfa]

Das Problem taucht jetzt komischerweise beim Best-Case auf (wenn alle Zahlen in der richtigen Reihenfolge sind...)
Ich kann das Feld mit den Zahlen nicht größer als 10000 machen, da mir Java ansonsten die Fehlermeldung:

Exception in thread "main" java.lang.StackOverflowError

Wenn du mit diesem Algorithmus ein sortiertes Array sortieren willst, wird Quicksort zum Slowsort. D.h. die Rekursionstiefe wächst mit n (also hier 10000). Und irgendwann ist der Stack voll und fliegt dir um die Ohren.
Den Stack zu vergrößern würde das Problem nicht lösen sondern nur später auftreten lassen.
Wähle das Pivot-Element besser (du nimmst immer das erste, fatal bei einer sortierten Liste). Du könntest z.B. das mittelgroße des ersten, letzten und mittleren Elements nehmen. Die Quicksort-Implementierung der Java-API nimmt sogar das mittlere von 9 gleichmäßig über das Array verteile Elemente, aber das halte ich für übertrieben.

 

[Landei]

Das ist nicht der "best case", sondern der "worst case": Beim Teilen bekommst du immer auf der einen Seite ein Intervall der Länge eins, und auf der anderen Seite den Rest. Beim Rest dasselbe ad infinitum. Da du die Methode rekursiv aufrufst, gibt es halt irgendwann einen Stack Overflow. Eine Möglichkeit, das "durchschnittliche" Verhalten zu verbessern, ist das Pivot-Element zufällig auszuwählen. Um einen Stack Overflow zu vermeiden, müsstest du statt der Rekursion eine Schleife nehmen, aber das ist in diesem Fall ziemlich unbequem.

Einige Sprachen vermeiden übrigens in vielen Fällen einen Stack Overflow durch sogenannte Tail Call (Recursion) Optimization - aber Java eben leider nicht.

 

[Leroy42]

Einige Sprachen vermeiden übrigens in vielen Fällen einen Stack Overflow durch sogenannte Tail Call (Recursion) Optimization - aber Java eben leider nicht.

Wie soll das denn bei Quicksort gehen? :shock:

Quicksort kann gar nicht endrekursiv sein, da es immer 2 rekursive Aufrufe
pro Rekursionsebene gibt. :noe:

Hier noch mal eine Erklärung der Endrekursion

 

[Guest]

So ich habe jetzt die Zeile

int pivot = daten[rechts];

aus der Methode teile
abgewandelt in

int pivot = daten[rechts/"];

sodass er hier das pivot Element immer als Mitte wählt...
Positiv anzumerken ist, dass er es hier immerhin bis zu einer Feldgröße von ungefähr 15000 schafft... aber immer noch zu wenig... Ich muss bis zu einer Feldgröße von 100.000 kommen...
Kann ich das Pivot-Element noch geschickter wählen?!

 

[Guest]

sry das sollte heißen

int pivot = daten[rechts/2];

 

[tfa]

rechts/2 ist aber nicht die Mitte.
Probier mal (rechts+links)/2

 

[Guest]

ich glaub ich liebe dich

Hat funktioniert
besten Dank an alle