Quicksort

Status
Nicht offen für weitere Antworten.

0001001

Bekanntes Mitglied
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:
Code:
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.
 
S

SlaterB

Gast
die Schleife sollte wohl eher kurz sein

Code:
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
Code:
for (int i = 0; i < a.length; i++) {
	System.out.print(a[i] + " ");
}
würde ich noch ein System.out.println(); setzen (Zeilenumbruch)
 

0001001

Bekanntes Mitglied
Vielen, vielen Dank! Hab in ein paar Stunden nicht geschafft was du innerhalb von einer Viertelstunde geschafft hast!
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
I Java Quicksort PAP Java Basics - Anfänger-Themen 2
B Quicksort in Verbindung mit einem Projekt Java Basics - Anfänger-Themen 1
M QuickSort und Liste Java Basics - Anfänger-Themen 6
S Laufzeit Quicksort wenn alle Elemente gleich sind Java Basics - Anfänger-Themen 4
G Quicksort Algorithmus Java Basics - Anfänger-Themen 12
Hanschyo Quicksort sortiert von groß nach klein Java Basics - Anfänger-Themen 3
R Quicksort mit Interface Comparable Java Basics - Anfänger-Themen 6
L Quicksort verstehen Java Basics - Anfänger-Themen 3
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 5
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 0
J Quicksort mit Stack Java Basics - Anfänger-Themen 4
Liondary Quicksort Java Basics - Anfänger-Themen 20
K Quicksort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
S Quicksort Algorithmus Java Basics - Anfänger-Themen 2
D Java Quicksort Java Basics - Anfänger-Themen 5
A Frage zu QuickSort Java Basics - Anfänger-Themen 9
B Quicksort mit Durchschnitt als Pivot Java Basics - Anfänger-Themen 1
K Quicksort Java Basics - Anfänger-Themen 3
M Quicksort - Probleme Java Basics - Anfänger-Themen 5
T QuickSort implementieren Java Basics - Anfänger-Themen 5
R QuickSort Verständis Problem (?) Java Basics - Anfänger-Themen 2
M Quicksort implementierung Java Basics - Anfänger-Themen 23
E Quicksort Java Basics - Anfänger-Themen 8
Xendarii Quicksort gibt kein Ergebnis aus Java Basics - Anfänger-Themen 13
E QuickSort: Ergebniss speichern Java Basics - Anfänger-Themen 2
P quickSort eines Objekt-Arrays geht nicht! Java Basics - Anfänger-Themen 11
F Stackoverflow bei Quicksort Java Basics - Anfänger-Themen 2
F Quicksort Java Basics - Anfänger-Themen 22
C Quicksort Invariante Java Basics - Anfänger-Themen 2
C QuickSort - Pivot in der Mitte Java Basics - Anfänger-Themen 5
P QuickSort iterativ Java Basics - Anfänger-Themen 5
K Eine Frage zum Quicksort Java Basics - Anfänger-Themen 11
B Quicksort --> Methodenaufruf Java Basics - Anfänger-Themen 10
B QuickSort - Fehler nicht zu finden Java Basics - Anfänger-Themen 2
W Quicksort Problem Java Basics - Anfänger-Themen 3
A Quicksort, #Vergleiche zählen klappt nicht Java Basics - Anfänger-Themen 3
J Quicksort Implementierung-- Exception ArrayOutOfBounds Java Basics - Anfänger-Themen 6
M Fehler in meinem Quicksort! Java Basics - Anfänger-Themen 21
B Quicksort Struktogramm Java Basics - Anfänger-Themen 9
G Frage zu Quicksort Java Basics - Anfänger-Themen 18
0 Quicksort bsp Java Basics - Anfänger-Themen 5
B Quicksort Problem Java Basics - Anfänger-Themen 6
S Mein Quicksort Problem: he method quickSort(int[], int, int) Java Basics - Anfänger-Themen 2
M Quicksort Java Basics - Anfänger-Themen 2
C Quicksort raten Java Basics - Anfänger-Themen 2
K ArrayList sortieren mit Quicksort Java Basics - Anfänger-Themen 3
M Quicksort Java Basics - Anfänger-Themen 4
J Quicksort programmieren Probleme Java Basics - Anfänger-Themen 9
S Quicksort Programm Java Basics - Anfänger-Themen 7
D Quicksort Java Basics - Anfänger-Themen 3
K Parameterübergabe bei quickSort Java Basics - Anfänger-Themen 6
S QuickSort will mir nicht in den Kopf (an einer Stelle) Java Basics - Anfänger-Themen 14
M QuickSort Java Basics - Anfänger-Themen 4
J QuickSort - kurze Frage Java Basics - Anfänger-Themen 9
H Quicksort und Rekursiv: Türme von Hanoi Java Basics - Anfänger-Themen 9

Ähnliche Java Themen

Neue Themen


Oben