Quicksort

[0001001]

Sorry, wenn ich euch mit meinen Sortieralgorithmen nerve, aber ich stecke mal wieder fest.

Hab quicksort implementiert, jedoch terminiert der algorithmus nicht und ich kann keinen fehler entdecken:

public class Quicksort {
	public void berechnen(int[] a, int l, int r ){	// erwartet das array und das den arrayanfang und das arrayende
		if (r > l) {	// falls r (das groesste element) groesser l (das kleineste element)
			/* (l+r) / 2 findet das mittlere element das zum pivot element wird und
			 *  vertauscht den inhalt des arrays an der stelle a[l+r/2] mit dem inhalt an der stelle a[l]
			 *  das bedeutet das das pivot element nach ganz vorne rueck			 * 
			 */
			swap(a, l, (l+r)/2);	
			int p = l;	// setzt den zeiger l auf das pivot element
			/* so lange i+1 kleiner r 
			 * auf deutsch: laufe vom anfang bis zum ende durch und schaue ob ein element a[i] kleiner ist als a[l]
			 * falls das der fall ist, tausche das element a[i] mit a[j], kopiere es also direkt nach das pivotelement
			 */
			for (int i=l+1; i<=r; ++i){
				if (a[i] < a[l]){
					swap(a, ++p, i);
				}
				/* wenn die for schleife einmal durchlaufen wurde stehen alle elemente die kleiner sind als das pivotelement (das ja
				 * noch an erster stelle im array steht) nach dem pivotelement. und a[l] zeigt auf das letzte kopierte element (das kleiner war
				 * als das pivotelement. darum wird jetzt dieses element mit dem pivotelement vertauscht, das heisst das pivotelement kommt an 
				 * seinen entgueltigen platz, weil ja alle elemente, die vorher kopiert wurden, kleiner waren als das pivotelement. 
				 */
				swap(a, l, p);
				/* Jetzt noch schnell quicksort rekursiv zweimal aufrufen fuer die beiden bereiche. quicksort bricht ab wenn r > l nicht
				 * mehr erfuellt ist. 
				 */
				berechnen(a, l, p-1);
				berechnen(a, p+1, r);					
				}
			}
		for (int i = 0; i < a.length; i++){
			System.out.print(a[i]+" ");
		}
		// return a;	
	}		
	
	void swap(int[]a, int i, int j){
	/* Vertauscht die Arrayelemente a[i] und a[j] */
		int x = a[i];
		a[i] = a[j];
		a[j] = x;
	}

}

Hab die Dokumentation extra dringelassen, damit man leichter versteht was der algorithmus machen soll.

 

[SlaterB]

die Schleife sollte wohl eher kurz sein

for (int i = l + 1; i <= r; ++i) {
	if (a[i] < a[l]) {
		swap(a, ++p, i);
	}
}

bei dir reicht sie noch viel weiter

----------

hinter

for (int i = 0; i < a.length; i++) {
	System.out.print(a[i] + " ");
}

würde ich noch ein System.out.println(); setzen (Zeilenumbruch)

 

[0001001]

Vielen, vielen Dank! Hab in ein paar Stunden nicht geschafft was du innerhalb von einer Viertelstunde geschafft hast!