class QuickSort {


// ----------------------------------------------------------------
    static void printArray(int a[], String msg) {


    System.out.println("-----------------------------------------");
    System.out.println(msg);

	for (int i=0; i < a.length; i++) {
	    System.out.println("a[" + i + "] = " + a[i]);
	}

    }

// ----------------------------------------------------------------
    static void swap(int a[], int le, int ri) {

	int aux = a[le];
	a[le] = a[ri];
	a[ri] = aux;

    }

// ----------------------------------------------------------------

    static int findPivotValue(int a[], int lo, int hi) {

	return a[(lo+hi)/2];


    }


// ----------------------------------------------------------------

    static void quickSort(int a[], int le, int ri) {

	int lo = le;
	int hi = ri;

        // Nur Sortierarbeit, wenn mindestens 2 Elemente im Array sind
	if ( lo < hi ) {

	    int mid = findPivotValue(a,le,ri);

            // Die Teile-Phase endet, wenn lo >= hi
	    while (lo <= hi) {

                // lo == ri kommt vor, wenn das Pivot Element
                // der groesste Wert im Array ist und 
                // nach a[ri] gelegt wurde.
		while (lo < ri && a[lo] < mid) lo = lo+1;
		while (le < hi && a[hi] > mid) hi = hi-1;

		if ( lo <= hi ) {

		    swap(a,lo,hi);
		    lo = lo+1;
		    hi = hi-1;

		}

		if ( le < hi ) quickSort(a,le,hi);
		if ( lo < ri ) quickSort(a,lo,ri);

	    }

	}

    }

// ----------------------------------------------------------------


    public static void main(String[] args) {


	//int a[] = { 2,7,4,6,3,9,8 };
	//int a[] = { 8,2,1,5,9,7,3 };
	int a[] = {5, 6, 3, 8, 9};

	printArray(a,"Unsortierter Array");

        // a = array, 0 = le (linker Index)
        // a.length -1 = ri (rechter Index)
	quickSort(a,0,a.length-1);

	printArray(a,"Sortierter Array");




    }
}