Bin dabei den QuickSort Algorithmus iterativ mit Hilfe von Stacks (Kellern) zu schreiben. Es funktioniert auch soweit ganz gut. Hin und wieder aber wird falsch sortiert. Ich bin mir sicher, dass ich k.pop() falsch gesetzt habe. Wenn ja, mir ist schleierhaft, wo das hingehört. Wenn nein, was könnte sonst falsch sein!?
Java:
public class QuickSortIterativ {
public static void sort(int[] zahlen) {
//neue Grenzen Objekte
Grenzen menge = new Grenzen();
Grenzen neueMenge = new Grenzen();
Grenzen.untereGrenze = 0;
Grenzen.obereGrenze = (zahlen.length-1);
Keller k = new VerweisKeller();
k.push(menge);
int tmp;
int i;
int j;
int mitte;
int x;
//solange der Keller nicht leer ist, soll sortiert werden
do {
//Casten da menge vom Typ Grenzen und k.top vom Typ Object
menge =(Grenzen) k.top();
k.pop();
i = menge.untereGrenze;
j = menge.obereGrenze;
mitte = (i+j) / 2;
x = zahlen[mitte];
do {
while(zahlen[i] < x) i++;
while(zahlen[j] > x) j--;
if(i <= j) {
tmp = zahlen[i];
zahlen[i] = zahlen[j];
zahlen[j] = tmp;
i++;
j--;
}
} while(i <= j);
//linke Haelfte sortieren
if(menge.untereGrenze < j) {
//Grenzen fuer diese Haelfte anpassen
neueMenge.untereGrenze = menge.untereGrenze;
neueMenge.obereGrenze = j;
//neue Grenzen auf den Keller legen
k.push(neueMenge);
}
//rechte Haelfte sortieren
if(i < menge.obereGrenze) {
//Grenzen fuer diese Haelfte anpassen
neueMenge.untereGrenze = i;
neueMenge.obereGrenze = menge.obereGrenze;
//neue Grenzen auf den Keller legen
k.push(neueMenge);
}
} while(!k.empty());
}
}
Java:
public class Grenzen {
public static int untereGrenze;
public static int obereGrenze;
}
Zuletzt bearbeitet:
