QuickSort iterativ

[pilx]

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!?

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());
	}
}

public class Grenzen {

	public static int untereGrenze;
	public static int obereGrenze;
	
}

 

[asdasdjk]

wenn du eine rekursive version hast, kannst du die andere genauso schreiben, indem du die parameter einfach übernimmst und diese kellerst...

 

[tagedieb]

Ich hab den Code mal rasch ueberflogen. Deine Grenzen Klasse ist falsch implementiert.
Die Variablen

untereGrenze

und

obereGrenze

sollte nicht static deklariert werden, sonst macht es gar keinen Sinn 2 Instanzen von Grenzen zu erzeugen wenn du nur statische Variablen hast.

Solche Zuweisungen von statischen Variablen sind sinnlos. Da kannst du auch irgendwo

i = i;

schreiben.

                neueMenge.untereGrenze = menge.untereGrenze;

Wenn du ein neues Grenzobjekt in den Keller legen willst musst du eine neue Instanz am Besten mit

new Grenzen(untereGrenze, obereGrenze)

erzeugen. Ansonsten legst du immer wieder diesebe Instanz in den Keller. Immer wenn du ein Wert einer Instanz aenderst, werden sich auch die Werte der andern 'Instanzen' aendern, da es ja dieselbe Instanz ist.

                //Grenzen fuer diese Haelfte anpassen
                //neueMenge.untereGrenze = menge.untereGrenze;
                //neueMenge.obereGrenze = j;
                //neue Grenzen auf den Keller legen
                k.push(new Grenzen(menge.untereGrenze, j));

Ich hoffe das bringt dich ein wenig weiter.

 

[pilx]

Vielen, vielen Dank.
Habe es jetzt wie folgt gemacht und es funktioniert hervorragend

public class QuickSortIterativ {

	public static void sort(int[] zahlen) {
		
		//neue Grenzen Objekte
		Grenzen menge = new Grenzen(0, 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
		while(!k.empty()) {
			
			//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) {
				
				//neue Grenzen auf den Keller legen
				k.push(new Grenzen(menge.untereGrenze, j));
				
			}
			
			//rechte Haelfte sortieren
			if(i < menge.obereGrenze) {
				
				//neue Grenzen auf den Keller legen
				k.push(new Grenzen(i, menge.obereGrenze));
				
			}
		}
	}
}

und die Grenzen

public class Grenzen {
  
  int untereGrenze;
  int obereGrenze;

  public Grenzen(int untereGrenze, int obereGrenze) {

    this.untereGrenze = untereGrenze;
    this.obereGrenze = obereGrenze;
	}
}

 

[asdasdjk]

eine klasse java.awt.Point würde es bereits geben, um die obere und unter grenze zu speichern und zu manipulieren
oder einfach ein new int[2] 🙂

 

[pilx]

Stehe ja in Java noch ganz am Anfang. Um die Konzepte besser zu verstehen usw. ist es wahrscheinlich doch besser sich nicht alles von Java zu importieren oder nicht?
Btw: gibt es in Java eigentlich auch eine Klasse, die für mich nach Quicksort (bzw. anderen Methoden) sortiert? Der ich dann einfach ein Array, Liste oder was auch immer übergebe und sie mir die sortierten Werte zurück gibt?