Quicksort Verständnisfrag

[Klösp]

Hallo

ich habe mal den Quicksort angeguckt.

Bin da aber an einer Stelle angelangt, wo ich nicht wirklich verstehe wieso es funktioniert.

Hab das ganze auch mal implementiert, gemäß dieser Erläuterung
http://stubber.math-inf.uni-greifswald.de/bioinformatik/folien07/Alg_Folien181-189.pdf

package packege1;

public class Quicksort {
	int[] array;
	int l, r;

	public Quicksort(int[] array) {
		this.array = array;
		this.l = 0;
		this.r = array.length - 1;
		sort(this.l, this.r, this.array);
	}

	public void sort(int l, int r, int[] array) {
		int pivot = array[(l + r) / 2];
		System.out.println(pivot);
		int i = l;
		int j = r;
		if (l < r) {
			while (i <= j) {
				while (i < r && array[i] < pivot) {
					i++;
				}

				while (j > l && array[j] > pivot) {
					j--;
				}

				if (i <= j) {
					swap(i, j);
					i++;
					j--;
				}
				if (i < r) {
					System.out.println("i="+i+" r="+r);
					sort(i, r, array);
				}
				if (l < j) {
					System.out.println("l="+l+" j="+j);
					sort(l, j, array);
				}
			}
		}
	}

	private void swap(int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] intarr = new int[] { 5,8,3,7,2,1,9};
		new Quicksort(intarr);
		for (int i : intarr) {
			System.out.println(i);
		}

	}

}

Was mich stört ist diese Stelle:

if (i < r) {
					sort(i, r, array);
				}
				if (l < j) {
					sort(l, j, array);
				}

Laut der Erläuterung ist wird nach dem ersten Durchlauf wie folgt aufgeteilt.
Teil 1: 0-4 Pivot hat dann den Wert 3
Teil 2: 5-6 Pivot hat dann der Wert 7

Wenn ich den Code ausführe bekomme ich aber folgende Aufteilung:
Laut der Erläuterung ist wird nach dem ersten Durchlauf wie folgt aufgeteilt.
Teil 1: 2-6 Pivot hat dann den Wert 2
Teil 2: 2-4 Pivot hat dann der Wert 2
Hier überschneiden sich die beiden Teile auch.

Das Ergebnis stimmt am Ende, aber wo liegt hier mein Denkfehler?


Danke im Vorraus

 

[Decrayer]

Liegt vielleicht an folgender Stelle:

                if (i <= j) {
                    swap(i, j);
                    i++;
                    j--;
                }
                if (i < r) {
                    System.out.println("i="+i+" r="+r);
                    sort(i, r, array);
                }
                if (l < j) {
                    System.out.println("l="+l+" j="+j);
                    sort(l, j, array);
                }

Wenn ich das mit dem Code aus den verlinkten Folien vergleiche, dann stehen die beiden if(i<r) sort... und if(l<j) sort... bei dir eine Ebene zu weit rechts, auf der gleichen Ebene wie if(i<=j) swap...

In den Folien kommen die beiden If's aber erst nach der while(i <= j) Schleife.