Fehler in meinem Quicksort!

[mamelinchen]

Mein Quicksort:

package a01;

public class QuickSortVerfahren {
	
	public static void tauscheWerte(int[]stapel,int a, int b){
		int helper=stapel[a];
		stapel[a]=stapel[b];
		stapel[b]=helper;
	}
	/******************************************************
	* Funktion zur Sortierung eines Feldes austeigend
	* Parameter:
	* @param- stapel: das zu sortierende Feld
	* @param- anfang: der Anfangswert des Feldes stapel
	* @param- ende:  der Endwert des Feldes stapel
	* Vorbedingung: R ist aufsteigend sortiert
	* @returnReturn: Sortiertes Feld aufsteigend,wenn Feld leer oder Größe 1,
	* dann wird das Feld stapel zurückgegeben
	* Effekt: -
	*****************************************************/
	

	public static void QuickSort(int[]stapel,int anfang,int ende){
		while (ende>anfang){
		
			int pivot=stapel[stapel.length-1];
			int j=ende;
			int i=anfang;
			
		while(i<=ende){
			i++;
		
			while(j>=anfang){
				j--;
		
				if(stapel[i]>pivot){// Wenn linkes El. grösser als Pivot und rechtes El.kleiner, dann tausche beide
					if(stapel[j]<pivot){
						System.out.println("JAJAJAJA");
						tauscheWerte(stapel,i,i);	
					}
				}
			}
		}
		if(i>=j){
			tauscheWerte(stapel,i,pivot);
			}
		QuickSort(stapel,anfang,pivot-1);
		QuickSort(stapel,pivot+1,ende);
		}
	}
	
	
	public static void main(String[] args) {
		int[]kleinarray=FileIntArray.FileToIntArray("../ALG1/src/a01/Rand20_1");
		QuickSort(kleinarray,0,19);
		for(int i=1;i<kleinarray.length;i++){
			System.out.println(kleinarray[i]);
		}
	}
}

Bloß das sich ein dummer Fehler eingeschlichen hat, und ich ihn net sehe.....!

Kann mir jemand weiterhelfen?

 

[MiDniGG]

Also bei mir wirfts da eine Exception nach der anderen. Erstmal kommt ne ArrayIndexOutOfBounds. Mach ich die weg kommt se wo anders wieder. Mach ich dann weiter und kommentier bissl was aus kommt ne StackOverflow, wegen dem rekursiven Aufruf der Quicksort-Methode...
Der Aufruf in der main-Methode ist auch nicht so geschickt, denn wenn mal mehr oder weniger als 19 zahlen im array stehen isses auch fürn arsch. da wäre ein kleinarray.length besser. So am Rande

 

[mamelinchen]

JA stimmt, bin bloß net drauf gekommen, ich seh das noch zu menschlich^^

Danke

 

[MiDniGG]

Naja. Dafür gibt's ja die Konsole die Dir alle Fehler rausschreibt

 

[mamelinchen]

Habs anders gemacht, geht aber immer noch nicht!

StackOverFlowError......

	public static void tauscheWerte(int[]stapel,int a, int b){
		int helper=stapel[a];
		stapel[a]=stapel[b];
		stapel[b]=helper;
	}
	/******************************************************
	* Funktion zur Sortierung eines Feldes austeigend
	* Parameter:
	* @param- stapel: das zu sortierende Feld
	* @param- anfang: der Anfangswert des Feldes stapel
	* @param- ende:  der Endwert des Feldes stapel
	* Vorbedingung: R ist aufsteigend sortiert
	* @returnReturn: Sortiertes Feld aufsteigend,wenn Feld leer oder Größe 1,
	* dann wird das Feld stapel zurückgegeben
	* Effekt: -
	*****************************************************/
	

	public static void QuickSort(int[] stapel, int anfang, int ende) {
		if (ende > anfang) {
			int pivot = stapel[stapel.length - 1];
			int i = anfang;
			int j = ende - 1;

			while (i <= j) {

				while (stapel[i] < pivot) {
					i++;
				}
				while (stapel[j] > pivot) {
					j--;
				}
				if (i <= j) {
					System.out.println("JAJAJAJA");
					tauscheWerte(stapel, i, j);
					i++;
					j--;
				}
			}
			if (i >= j) {
				tauscheWerte(stapel, i, pivot);
			}
			QuickSort(stapel, anfang, i);
			QuickSort(stapel, i + 1, ende);
		}
	}

WO ist der Fehler?

 

[MiDniGG]

Ich hab kein Plan und will mich jetzt nicht reindenken. Aber vllt hilft Dir ja mein Code den ich irgendwann mal geschrieben hab ^^

	public static int[] quickSortAlgo(int[] arr) {
		int wert = getPivotElement(arr);
		int[] links = new int[arr.length];
		int[] rechts = new int[arr.length];
		int l = 0;
		int r = 0;
		for(int i = 0; i < arr.length; i++) // erster sortiervorgang aller
											// Zahlen die größer als Mitte sind
											// nach rechts
		{ // alle Zahlen die kleiner sind nach links
			if(arr[i] <= wert) {
				links[l] = arr[i];
				l++;
			} else {
				rechts[r] = arr[i];
				r++;
			}
		}
		int[] temp = new int[l];
		System.arraycopy(links, 0, temp, 0, temp.length);
		links = new int[temp.length];
		System.arraycopy(temp, 0, links, 0, links.length);
		temp = new int[r];
		System.arraycopy(rechts, 0, temp, 0, temp.length);
		rechts = new int[temp.length];
		System.arraycopy(temp, 0, rechts, 0, rechts.length);
		if(links.length > 1 && !isRepeatingNumber(links)) {
			links = quickSortAlgo(links);
		}
		if(rechts.length > 1 && !isRepeatingNumber(rechts)) {
			rechts = quickSortAlgo(rechts);
		}
		temp = new int[arr.length];
		System.arraycopy(links, 0, temp, 0, l);
		System.arraycopy(rechts, 0, temp, l, r);
		return temp; // bearbeitetes Array wird zurückgegeben
	}
	private static int getPivotElement(int[] array) {
		int count = 0;
		for(int i = 0; i < array.length; i++) {
			count += array[i];
		}
		return count / array.length;
	}
	private static boolean isRepeatingNumber(int[] array) {
		for(int i = 1; i < array.length; i++) {
			if(array[i] != array[i - 1]) {
				return false;
			}
		}
		return true;
	}

 

[mamelinchen]

Danke

 

[mamelinchen]

public class QuickSortVerfahren {
	
	/******************************************************
	* Funktion zum Vertauschen von zwei Werten eines Arrays
	* Parameter:
	* @param- stapel: das Feld
	* @param- a: der erste Wert des Feldes stapel
	* @param- b:  der zweite Wert des Feldes stapel
	* @returnReturn: -
	* Effekt: die Werte des Stapels sind vertauscht
	*****************************************************/
	
	public static void tauscheWerte(int[]stapel,int a, int b){
		System.out.println(stapel[b]);
		int helper=stapel[a];                    // Hilfsvariable zum Vertauschen
		stapel[a]=stapel[b];
		stapel[b]=helper;
	}
	
	/******************************************************
	* Funktion zur Sortierung eines Feldes austeigend
	* Parameter:
	* @param- stapel: das zu sortierende Feld
	* @param- anfang: der Anfangswert des Feldes stapel
	* @param- ende:  der Endwert des Feldes stapel
	* Vorbedingung: R ist aufsteigend sortiert
	* @returnReturn: Sortiertes Feld aufsteigend,wenn Feld leer oder Größe 1,
	* dann wird das Feld stapel zurückgegeben
	* Effekt: -
	*****************************************************/
	

	public static void QuickSort(int[] stapel, int anfang, int ende) {
		if (ende > anfang) {
			int pivot = stapel[stapel.length-1];	//Pivotelement ist das Element am rechten Rand des Feldes
			int i = anfang;							//Rechter Index
			int j = ende-1;						//Linker Index

			while (i < j) {						//Wiederhole solange, wie die Indexe sich nicht überschneiden

				while (stapel[i] <= pivot && i < ende) {//Erhöhe Index i solange, bis der Wert an Index i kleiner ist, als das Pivotelement
					i++;
				}
				while (stapel[j] >= pivot && j> anfang) {			//Verringere Index j solange, bis der Wert an Index j grösser ist, als das Pivotelement
					j--;
				}
				if(i < j){
					tauscheWerte(stapel, i, j);     //Tausche die Werte, auf die i und j zeigen
					i++;			//Erhöhe Index i, um nächsten Wert zu prüfen
					j--;			//Verringere Index j, um nächsten Wert zu prüfen
				}
			}
			if (stapel[i] > pivot) {   		//Wenn Wert i in Array größer ist,als das Pivotelement,setze Pivot an endgültige Stelle
				tauscheWerte(stapel, i, pivot);
			}
			QuickSort(stapel, anfang, i+1);	//Anwendung von Quicksort auf dem rechten Abschnitt
			QuickSort(stapel, i -1, ende);	//Anwendung von Quicksort auf dem linken Abschnitt
		}
	}

	public static void main(String[] args) {
		int[] kleinarray = FileIntArray.FileToIntArray("../ALG1/src/a01/Rand20_1");
		QuickSort(kleinarray, 0, kleinarray.length);
//		for (int i = 0; i < kleinarray.length; i++) {
//			System.out.println(kleinarray[i] + "");
//		}
	}
}

An einer Stelle bleibt er hängen und vertauscht die Werte hin und her.
Die letzten Werte, die das Kriterium erfüllen..

Aber Wo Wieso Warum!?

 

[SlaterB]

alle anderen sollen nun also tage-, wenn nicht wochenlang tausende Test-Fälle zusammenbasteln,
bis sie eine Konstellation finden, bei der es zu einem komplizierten Fehler kommt

ODER

du postest genau, welche Eingabe verwendest,
(total simpel: int[] kleinarray = new int[] {4, 5, 1, 3}; wozu die Datei in der Testphase?)
+ wann es wo zu welchem Fehler kommt

 

[mamelinchen]

int[] {16, 4, 13, 19, 9, 10, 5,5,2,7,14,18,16,19,6,15,2,10,11,13}

13 ist mein Pivot.

Der Fehler liegt hier:

{16, 4, 13, 19, 9, 10, 5,5,2,7,14,18,16,19,6,15,2,10,11,13}

Er vertauscht die beiden immer wieder, obwohl ich den Zeiger von beiden erhöhe und die while Schleife oben eigentlich nicht fassen sollte, da dann i>j!!

Aber er machts trotzdem.

 

[mamelinchen]

Datei, da wir Arrays mit 10000 Werten,......usw. sortieren sollen.

 

[SlaterB]

ich hab jetzt bisschen angefangen zu debuggen, aber da kommen eher immer mehr Fehler als dass was zu deinem zu finden wäre,
Beispiel:
> tauscheWerte(stapel, i, pivot);
pivot ist der WERT, übergeben werden muss aber der INDEX im Array

--------

> while (stapel <= pivot && i < ende) {
> i++;
> }

wenn das pivot der kleinste Wert ist, wird i bis zum Maximum erhöht und es gibt eine ArrayIndexOutOfBoundException,
die Abfrage 'i < ende' muss doch VOR dem Array-Zugriff stattfinden

--------

wieso ist das Pivot-Element immer das Ende des Arrays?
wenn man nur die erste Hälfte sortiert, kann man doch nur daraus etwas wählen, nicht auf fremde Teile des Arrays zugreifen

usw.
von den laufenden Exceptions wird man drauf hingewiesen, mit System.out.println alles zu debuggen,
Tipp: fange mit kurzen Arrays wie {16, 4, 13, 1} an

 

[mamelinchen]

wenn das pivot der kleinste Wert ist, wird i bis zum Maximum erhöht und es gibt eine ArrayIndexOutOfBoundException,
die Abfrage 'i < ende' muss doch VOR dem Array-Zugriff stattfinden

aber mit && drücke ich doch aus ,das beide Bedingungen erfüllt sein müssen?
i<ende UND stapel <= pivot,oder?

 

[SlaterB]

Reihenfolge ist wichtig, erst auf Grenze prüfen, damit der zweite Test nicht ausgeführt werden muss,

erst der Array-Zugriff führt dagegen zur Exception

vergleiche mit:
Abzug drücken && Pistole entladen
vs
Pistole entladen && Abzug drücken

 

[mamelinchen]

Ahhhhh verstehe...

Hab ich gemacht.Auch das mit dem pivot und debugge grade.

Er führt jetzt den rekursiven Quicksort tausendmal aus.(habs net gezählt)

Setzte die Grenze zwar mit
QuickSort(stapel, anfang, i), da ja dann i als pivot -1 definiert wird,also eine Stelle vor dem vorherigen Pivot.
Mein Fehler ist jetzt, das er den linken Zähler dauernd erhöht , da die Werte ALLE kleiner sind als das neue Pivot!

Was mach ich n nu?

 

[SlaterB]

schau nach, was der Original-Algorithmus dazu sagt, wahrscheinlich sollte ja wenigstens ein Element abgetrennt werden, und sei es der Pivot,
dann muss die Restliste (Länge-1) sortiert werden, mit neuem Pivot, wie ich schon angemerkt hatte,

im schlimmsten Fall passiert das n-Mal hintereinander, aber so das ist eben bei Quicksort, Worstcase ist eine bereits sortierte Liste,
spätestens nach n Runden ist man dennoch fertig, Endlosschleife ausgeschlossen, falls korrekt umgesetzt

 

[mamelinchen]

package a01;

public class QuickSortVerfahren {
	
	/******************************************************
	* Funktion zum Vertauschen von zwei Werten eines Arrays
	* Parameter:
	* @param- stapel: das Feld
	* @param- a: der erste Wert des Feldes stapel
	* @param- b:  der zweite Wert des Feldes stapel
	* @returnReturn: -
	* Effekt: die Werte des Stapels sind vertauscht
	*****************************************************/
	
	public static void tauscheWerte(int[]stapel,int a, int b){
		System.out.println(stapel[a]);
		System.out.println(stapel[b]);
		int helper=stapel[a];                    // Hilfsvariable zum Vertauschen
		stapel[a]=stapel[b];
		stapel[b]=helper;
	}
	
	/******************************************************
	* Funktion zur Sortierung eines Feldes austeigend
	* Parameter:
	* @param- stapel: das zu sortierende Feld
	* @param- anfang: der Anfangswert des Feldes stapel
	* @param- ende:  der Endwert des Feldes stapel
	* Vorbedingung: R ist aufsteigend sortiert
	* @returnReturn: Sortiertes Feld aufsteigend,wenn Feld leer oder Größe 1,
	* dann wird das Feld stapel zurückgegeben
	* Effekt: -
	*****************************************************/
	

	public static void QuickSort(int[] stapel, int anfang, int ende) {
		if (ende > anfang) {
			int pivot = stapel[ende-1];	//Pivotelement ist das Element am rechten Rand des Feldes
			int i = anfang;							//Rechter Index
			int j = ende-1;						//Linker Index

			while (i < j) {						//Wiederhole solange, wie die Indexe sich nicht überschneiden

				while ( i < ende && stapel[i] <= pivot ) {//Erhöhe Index i solange, bis der Wert an Index i kleiner ist, als das Pivotelement
					i++;
				}
				while (j> anfang && stapel[j] >= pivot) {//Verringere Index j solange, bis der Wert an Index j grösser ist, als das Pivotelement
					j--;
				}
				if(i < j){
					tauscheWerte(stapel, i, j);     //Tausche die Werte, auf die i und j zeigen
				}
			}
			if (stapel[i] > pivot) {  
				tauscheWerte(stapel, i, ende-1);//Wenn Wert i in Array größer ist,als das Pivotelement,setze Pivot an endgültige Stelle
			}

			QuickSort(stapel, anfang, i);	//Anwendung von Quicksort auf dem rechten Abschnitt
			QuickSort(stapel, i+1 , ende);	//Anwendung von Quicksort auf dem linken Abschnitt
		}
	}

	public static void main(String[] args) {
		int[] kleinarray = FileIntArray.FileToIntArray("../ALG1/src/a01/Rand20_1");
		QuickSort(kleinarray, 0, kleinarray.length);
//		for (int i = 0; i < kleinarray.length; i++) {
//			System.out.println(kleinarray[i] + "");
//		}
	}
}

Sortier das erste ma perfekt, danach vertauscht er das Pivot {6}
(alle Werte grösser und kleiner)
und tauscht es aber nochmals mit einem Wert vorher im Arrray, der kleiner ist.{5}

WIESO!!!

Das kann doch net sein!

Werte von Anfang an:
OriginalArray
16
4
13
19
9
10
5
5
2
7
14
18
16
19
6
15
2
10
11
13
:____________

16}Zu tauschende Elemente
11}
19
10
14
2
18
6
16
13
_______
linkes Teilarray
11
2
13
2
10
5
9
5
10
6Pivottausch
6???????
5???????

Ick versteh dit nich.

 

[SlaterB]

schlechtes Log, das kann man so schön machen:

package testmain;

import java.io.Serializable;

public class Test implements Serializable {

	public static void main(String argv[]) throws Exception {
		int[] kleinarray = new int[] { 16, 4, 13, 19, 9, 10, 5, 5, 2, 7, 14,
				18, 16, 19, 6, 15, 2, 10, 11, 13 };
		QuickSortVerfahren.QuickSort(kleinarray, 0, kleinarray.length);
		// for (int i = 0; i < kleinarray.length; i++) {
		// System.out.println(kleinarray[i] + "");
		// }

	}
}

class QuickSortVerfahren {

	/***************************************************************************
	 * Funktion zum Vertauschen von zwei Werten eines Arrays Parameter:
	 * 
	 * @param- stapel: das Feld
	 * @param- a: der erste Wert des Feldes stapel
	 * @param- b: der zweite Wert des Feldes stapel
	 * @returnReturn: - Effekt: die Werte des Stapels sind vertauscht
	 **************************************************************************/

	public static void tauscheWerte(int[] stapel, int a, int b) {
		System.out.println("tausche " + stapel[a] + ", " + stapel[b]
				+ " (Indexe " + a + ", " + b + ")");
		int helper = stapel[a]; // Hilfsvariable zum Vertauschen
		stapel[a] = stapel[b];
		stapel[b] = helper;
	}

	/***************************************************************************
	 * Funktion zur Sortierung eines Feldes austeigend Parameter:
	 * 
	 * @param- stapel: das zu sortierende Feld
	 * @param- anfang: der Anfangswert des Feldes stapel
	 * @param- ende: der Endwert des Feldes stapel Vorbedingung: R ist
	 *         aufsteigend sortiert
	 * @returnReturn: Sortiertes Feld aufsteigend,wenn Feld leer oder Größe 1,
	 *                dann wird das Feld stapel zurückgegeben Effekt: -
	 **************************************************************************/

	public static void QuickSort(int[] stapel, int anfang, int ende) {
		String info = "quicksort " + anfang + ", " + ende + ", Array: ";
		for (int i = anfang; i < ende; i++) {
			info += stapel[i] + ", ";
		}
		System.out.println(info);
		try {
			Thread.sleep(100);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		if (ende > anfang) {
			int pivot = stapel[ende - 1]; // Pivotelement ist das Element am
			System.out.println("pivot: " + pivot);
			// rechten Rand des Feldes
			int i = anfang; // Rechter Index
			int j = ende - 1; // Linker Index

			while (i < j) { // Wiederhole solange, wie die Indexe sich nicht
				// überschneiden

				while (i < ende && stapel[i] <= pivot) {// Erhöhe Index i
					// solange, bis der Wert
					// an Index i kleiner
					// ist, als das
					// Pivotelement
					i++;
				}
				while (j > anfang && stapel[j] >= pivot) {// Verringere Index
					// j solange, bis
					// der Wert an Index
					// j grösser ist,
					// als das
					// Pivotelement
					j--;
				}
				if (i < j) {
					tauscheWerte(stapel, i, j); // Tausche die Werte, auf die i
					// und j zeigen
				}
			}
			if (stapel[i] > pivot) {
				tauscheWerte(stapel, i, ende - 1);// Wenn Wert i in Array
				// größer ist,als das
				// Pivotelement,setze Pivot
				// an endgültige Stelle
			}

			QuickSort(stapel, anfang, i); // Anwendung von Quicksort auf dem
			// rechten Abschnitt
			QuickSort(stapel, i + 1, ende); // Anwendung von Quicksort auf dem
			// linken Abschnitt
		}
	}
}

Ausgabe:

quicksort 0, 20, Array: 16, 4, 13, 19, 9, 10, 5, 5, 2, 7, 14, 18, 16, 19, 6, 15, 2, 10, 11, 13, 
pivot: 13
tausche 16, 11 (Indexe 0, 18)
tausche 19, 10 (Indexe 3, 17)
tausche 14, 2 (Indexe 10, 16)
tausche 18, 6 (Indexe 11, 14)
tausche 16, 13 (Indexe 12, 19)
quicksort 0, 12, Array: 11, 4, 13, 10, 9, 10, 5, 5, 2, 7, 2, 6, 
pivot: 6
tausche 11, 2 (Indexe 0, 10)
tausche 13, 2 (Indexe 2, 8)
tausche 10, 5 (Indexe 3, 7)
tausche 9, 5 (Indexe 4, 6)
tausche 10, 6 (Indexe 5, 11)
quicksort 0, 5, Array: 2, 4, 2, 5, 5, 
pivot: 5
tausche 6, 5 (Indexe 5, 4)
quicksort 0, 5, Array: 2, 4, 2, 5, 6, 
pivot: 6
quicksort 0, 5, Array: 2, 4, 2, 5, 6, 
pivot: 6
quicksort 0, 5, Array: 2, 4, 2, 5, 6, 
pivot: 6
.........

was stört dich am letzten Tausch von 6 und 5, finde ich logisch,
danach wird allerdings für alle Zeit bzw. bis zu einer StackOverflowException
quicksort 0, 5 aufgerufen,

wie ich gesagt habe: wenn das Pivot ein Randelement ist, dann muss man doch wenigstens ein Element abziehen und nur noch eine kleinere Menge sortieren,
überlege, ob du das bisher implementiert hast, wenn nicht, dann tue es, wenn doch, dann schaue dir die Schleife genau an,
wann wo warum i und j erhöht oder gesenkt werden

 

[SlaterB]

edit: nicht so sinnvoll was hier stand

nochmal neu:
wenn ich deinen Code mit
Quicksort ? Wikipedia
vergleiche, dann sehe ich dort
> pivot := daten[rechts]
> wiederhole solange daten ≤ pivot und i < rechts

während du
> pivot = stapel[ende - 1];
> while (i < ende && stapel <= pivot)
hast

das passt nicht zusammen, daher wahrscheinlich auch die ArrayOutOfBoundException und die umzudrehende Reihenfolge der while-Bedingungen,
der ende-Index muss wohl generell um 1 kleiner

 

[mamelinchen]

Weil die 6 vor die 5 kommt, und das ist nicht sortiert....

Tolle Ausgabe

Reihenfolge ist wichtig, erst auf Grenze prüfen, damit der zweite Test nicht ausgeführt werden muss,

erst der Array-Zugriff führt dagegen zur Exception

vergleiche mit:
Abzug drücken && Pistole entladen
vs
Pistole entladen && Abzug drücken

Ich dachte?


Das von Wicki hat ich auch schon, geht nicht.

 

[SlaterB]

ich verstehe in deiner Antwort jetzt nicht allzu viel,
hier aber noch eine sortierende Version wie im Wiki, mit einfachen Änderungen zu -1, die ich schon angesprochen hatte

public class Test implements Serializable {

	public static void main(String argv[]) throws Exception {
		int[] kleinarray = new int[] { 16, 4, 13, 19, 9, 10, 5, 5, 2, 7, 14,
				18, 16, 19, 6, 15, 2, 10, 11, 13 };
		QuickSortVerfahren.QuickSort(kleinarray, 0, kleinarray.length - 1);
		System.out.println("sortiert: " + Arrays.toString(kleinarray));

	}
}

class QuickSortVerfahren {

	/***************************************************************************
	 * Funktion zum Vertauschen von zwei Werten eines Arrays Parameter:
	 * 
	 * @param- stapel: das Feld
	 * @param- a: der erste Wert des Feldes stapel
	 * @param- b: der zweite Wert des Feldes stapel
	 * @returnReturn: - Effekt: die Werte des Stapels sind vertauscht
	 **************************************************************************/

	public static void tauscheWerte(int[] stapel, int a, int b) {
		System.out.println("tausche " + stapel[a] + ", " + stapel[b]
				+ " (Indexe " + a + ", " + b + ")");
		int helper = stapel[a]; // Hilfsvariable zum Vertauschen
		stapel[a] = stapel[b];
		stapel[b] = helper;
	}

	/***************************************************************************
	 * Funktion zur Sortierung eines Feldes austeigend Parameter:
	 * 
	 * @param- stapel: das zu sortierende Feld
	 * @param- anfang: der Anfangswert des Feldes stapel
	 * @param- ende: der Endwert des Feldes stapel Vorbedingung: R ist
	 *         aufsteigend sortiert
	 * @returnReturn: Sortiertes Feld aufsteigend,wenn Feld leer oder Größe 1,
	 *                dann wird das Feld stapel zurückgegeben Effekt: -
	 **************************************************************************/

	public static void QuickSort(int[] stapel, int anfang, int ende) {
		String info = "quicksort " + anfang + ", " + ende + ", Array: ";
		for (int i = anfang; i <= ende; i++) {
			info += stapel[i] + ", ";
		}
		System.out.println(info);
		try {
			Thread.sleep(100);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		if (ende > anfang) {
			int pivot = stapel[ende]; // Pivotelement ist das Element am
			System.out.println("pivot: " + pivot);
			// rechten Rand des Feldes
			int i = anfang; // Rechter Index
			int j = ende - 1; // Linker Index

			while (i < j) { // Wiederhole solange, wie die Indexe sich nicht
				// überschneiden

				while (i < ende && stapel[i] <= pivot) {// Erhöhe Index i
					// solange, bis der Wert
					// an Index i kleiner
					// ist, als das
					// Pivotelement
					i++;
				}
				while (j > anfang && stapel[j] >= pivot) {// Verringere Index
					// j solange, bis
					// der Wert an Index
					// j grösser ist,
					// als das
					// Pivotelement
					j--;
				}
				if (i < j) {
					tauscheWerte(stapel, i, j); // Tausche die Werte, auf die i
					// und j zeigen
				}
			}
			if (stapel[i] > pivot) {
				tauscheWerte(stapel, i, ende);// Wenn Wert i in Array
				// größer ist,als das
				// Pivotelement,setze Pivot
				// an endgültige Stelle
			}

			QuickSort(stapel, anfang, i - 1); // Anwendung von Quicksort auf
												// dem
			// rechten Abschnitt
			QuickSort(stapel, i + 1, ende); // Anwendung von Quicksort auf dem
			// linken Abschnitt
		}
	}
}

für deine 10.000-Datei die Log-Ausgaben und vor allem das Thread.sleep(100) besser ausbauen

 

[mamelinchen]

Ahhhhhhhhhhhhhhhhh klappt alles wunderbar!!


Und 100000 geht auch!


Was hast du gemacht?!?!?!

SIEHT NCIH ANDERS AUS ALS MEINS,

oder doch?

DANKEEEEE DANKE