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:
Hab die Dokumentation extra dringelassen, damit man leichter versteht was der algorithmus machen soll.
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.