J
jhjp
Gast
Hallihallo,
also ich hab die Aufgabe nen QuickSort Algorithmus zu programmieren! Habs auch gemacht, siehe unten. Der Code funktioniert auch, jedoch nur für Felder mit der Länge 14. Bei längeren Feldern kommt ein StackOverflowError.
Wahrscheinlich weil die Rekursion zu tief geht! Liege ich in dieser Annahme richtig?????
und noch ne Frage: Ist das ein Algorithmus im Sinne des QuickSort???
(Hab vom Prof. zwar ne Vorlage bekommen, kann die aber nicht implementieren, weil er in einer Methode 2 Rückgabewerte macht, und ich weiß nicht wie man das in Java umsetzt.. :cry: )
Also hier mein Code (Bin ganz stolz darauf, habs in 20Minuten programmiert und es hat fast auf anhieb funktioniert)
gruß
beni
also ich hab die Aufgabe nen QuickSort Algorithmus zu programmieren! Habs auch gemacht, siehe unten. Der Code funktioniert auch, jedoch nur für Felder mit der Länge 14. Bei längeren Feldern kommt ein StackOverflowError.
Wahrscheinlich weil die Rekursion zu tief geht! Liege ich in dieser Annahme richtig?????
und noch ne Frage: Ist das ein Algorithmus im Sinne des QuickSort???
(Hab vom Prof. zwar ne Vorlage bekommen, kann die aber nicht implementieren, weil er in einer Methode 2 Rückgabewerte macht, und ich weiß nicht wie man das in Java umsetzt.. :cry: )
Also hier mein Code (Bin ganz stolz darauf, habs in 20Minuten programmiert und es hat fast auf anhieb funktioniert)
Code:
public static int[] QuickSort(int[] f){
if(f.length == 1) return f;
else{
int p = pivotzerlegung(f);
int f1length = lengthkleinergleich(f, p);
int f2length = lengthgroesser(f, p);
int[] f1 = new int[f1length];
int[] f2 = new int[f2length];
int if1 = 0; int if2 = 0;
for(int i=0; i<f.length; i++){
if(f[i] <= p){
f1[if1] = f[i];
if1++;
}
else{
f2[if2] = f[i];
if2++;
}
}
return combine( QuickSort(f1), QuickSort(f2) );
}
}
private static int pivotzerlegung(int[] f){
int summe = 0;
for(int i=0; i<f.length; i++) summe += f[i];
return summe/f.length;
}
private static int lengthkleinergleich(int[] f, int p){
int summekleinergleich = 0;
for(int i=0; i<f.length; i++) if(f[i] <= p) summekleinergleich++;
return summekleinergleich;
}
private static int lengthgroesser(int[] f, int p){
int summegroesser = 0;
for(int i=0; i<f.length; i++) if(f[i] > p) summegroesser++;
return summegroesser;
}
private static int[] combine(int[] f1, int[] f2){
int[] neu = new int[f1.length + f2.length];
for(int i=0; i<f1.length; i++) neu[i] = f1[i];
for(int i=0; i<f2.length; i++) neu[f1.length + i] = f2[i];
return neu;
}
beni