Quicksort Problem

[wolfheart]

Hallo, ich habe hier einen Quicksortcode der fast funktioniert, aber nur fast... Aus irgendeinem Grund werden nicht alle Zahlen sortiert, was ist hier falsch:

public class AufgabeQuicksort {

	public static void main(String[] args) {
		 int[] array = {1, 3, 7, 2, 4, 8, 9, 6, 5};
		// int[] array = {3, 2};
		// int[] array = {2, 0, 2, 0, 5, 4};
		// int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 2};
		// int[] array = {44, 6, 55, 30, 94, 18};

		int u = 0; // lowest array-element
		int o = array.length - 1; // highest array-element

		println("Unsorted Array: ");
		for (int l = 0; l < array.length; l++) {
			if (l < array.length - 1)
				System.out.print(array[l] + ",");
			else
				System.out.println(array[l]);
		}

		quicksortAlg(array, u, o);

		System.out.println("Finished: ");
		for (int l = 0; l < array.length; l++) {
			if (l < array.length - 1)
				System.out.print(array[l] + ",");
			else
				System.out.println(array[l]);
		}
	}

	// ============== Quicksort algorithm ================
	public static void quicksortAlg(int[] sortArray, int u, int o) {
		int index;
		System.out.println("o: " + o);
		if (o > u + 1) {
			index = partition(sortArray, u, o);
			u = index;
			quicksortAlg(sortArray, index++, o);
			quicksortAlg(sortArray, u, index--);
		}
	}

	// ==================== Function partition ====================
	public static int partition(int[] arrayDivide, int u, int o) {
		int index = u;
		int p = o; // Index from pivot-element

		System.out.print("Pivot-element: " + arrayDivide[p] + " |");

		for (int pointer = u; pointer < o; pointer++) {
			if (arrayDivide[pointer] <= arrayDivide[p]) {
				swap(arrayDivide, index, pointer);
				index++;
			}
		}
		swap(arrayDivide, index, p);

		// print arrayDivide on the console
		for (int l = 0; l < arrayDivide.length; l++) {
			if (l < arrayDivide.length - 1)
				System.out.print(arrayDivide[l] + ",");
			else
				System.out.println(arrayDivide[l]);
		}
		return index;
	}

	// ======== Function to switch array-elements ==============
	public static void swap(int[] arraySwap, int idx1, int idx2) {
		int tmp = arraySwap[idx1];
		arraySwap[idx1] = arraySwap[idx2];
		arraySwap[idx2] = tmp;
	}
}

Beispiel: 3 und 2 werden nicht vertauscht

Unsorted Array: 
1,3,7,2,4,8,9,6,5
o: 8
Pivot-element: 5 |1,3,2,4,5,8,9,6,7
o: 8
Pivot-element: 7 |1,3,2,4,5,6,7,8,9
o: 8
Pivot-element: 9 |1,3,2,4,5,6,7,8,9
o: 8
o: 9
o: 7
o: 5
Finished: 
1,3,2,4,5,6,7,8,9

Beispiel: hier wird nur die 4 mit der 5 vertauscht

Unsorted Array: 
2,0,2,0,5,4
o: 5
Pivot-element: 4 |2,0,2,0,4,5
o: 5
o: 5
Finished: 
2,0,2,0,4,5

 

[SlaterB]

und du kannst am Code rein gar nix erkennen, weiter debuggen?

public static void quicksortAlg(int[] sortArray, int u, int o) {
        int index;
        System.out.println("o: " + o);
        if (o > u + 1) {
            index = partition(sortArray, u, o);
            u = index;
            quicksortAlg(sortArray, index++, o);
            quicksortAlg(sortArray, u, index--);
        }
    }

die Methode beginnt im ersten Schritt noch ganz nett mit u=0, o = max
dann kommt irgendein index aus, ganz egal welcher irgendwas mittleres,
durch u = index; sind u und index offensichtlich ziemlich das gleiche, wozu das?!

und was steht noch dahinter?
> quicksortAlg(sortArray, index++, o);
na gut, kann man ungefähr als 'sortiere den oberen Teil verstehen'
aber dann
> quicksortAlg(sortArray, u, index--);
u ist doch sowieso ungefähr gleich index, was soll dieser Befehl machen? zumal u und index alle potentiell mittlere bis hohe Zahlen sind,
der Bereich von 0 an (vom alten u an) wird gänzlich ignoriert

die Zeile
> u = index;
scheint ohne jeden Sinn zu sein, die kann man komplett streichen, das alte u muss gemerkt werden,
dann noch die nächsten beiden Zeilen in
quicksortAlg(sortArray, index + 1, o);
quicksortAlg(sortArray, u, index - 1);
umwandeln, schon scheint es zu laufen, index++ usw. ist sehr gefährlich, damit wird die index-Variable geändert


edit: {3,2} wird noch nicht sortiert, auch wenn ein Teilbereich nur zwei Zahlen hat, könnte der durch die Bedingung if (o > u + 1) übersprungen werden

 

[wolfheart]

Vielen Dank!

Hab das mit index geändert und jetzt sortiert er weiter, aber leider immer noch nicht ganz bis zum schluss ich dreh noch durch

Beispiel:

Unsorted Array: 
10,4,33,44,17,20,3,2,9,82,38,67,55,11,32,23,19,7,6,14,29
o: 20
Pivot-element: 29 |10,4,17,20,3,2,9,11,23,19,7,6,14,29,32,33,82,38,67,55,44
o: 20
Pivot-element: 44 |10,4,17,20,3,2,9,11,23,19,7,6,14,29,32,33,38,44,67,55,82
o: 20
Pivot-element: 82 |10,4,17,20,3,2,9,11,23,19,7,6,14,29,32,33,38,44,67,55,82
o: 20
o: 19
o: 16
Pivot-element: 38 |10,4,17,20,3,2,9,11,23,19,7,6,14,29,32,33,38,44,67,55,82
o: 16
o: 15
o: 12
Pivot-element: 14 |10,4,3,2,9,11,7,6,14,19,17,20,23,29,32,33,38,44,67,55,82
o: 12
Pivot-element: 23 |10,4,3,2,9,11,7,6,14,19,17,20,23,29,32,33,38,44,67,55,82
o: 12
o: 11
Pivot-element: 20 |10,4,3,2,9,11,7,6,14,19,17,20,23,29,32,33,38,44,67,55,82
o: 11
o: 10
o: 7
Pivot-element: 6 |4,3,2,6,9,11,7,10,14,19,17,20,23,29,32,33,38,44,67,55,82
o: 7
Pivot-element: 10 |4,3,2,6,9,7,10,11,14,19,17,20,23,29,32,33,38,44,67,55,82
o: 7
o: 5
o: 2
Pivot-element: 2 |2,3,4,6,9,7,10,11,14,19,17,20,23,29,32,33,38,44,67,55,82
o: 2
o: -1
Finished: 
2,3,4,6,9,7,10,11,14,19,17,20,23,29,32,33,38,44,67,55,82

 

[SlaterB]

edit: {3,2} wird noch nicht sortiert, auch wenn ein Teilbereich nur zwei Zahlen hat, könnte der durch die Bedingung if (o > u + 1) übersprungen werden

?
bisschen arbeiten darfst du auch noch, z.B. die Bedingung modifizieren

falls du das schon gemacht hast und 3,2 funktioniert, dann bitte darauf hinweisen + neuen Code, dann kann ich nochmal nachschauen