/**
 *  @file Quicksort 
 *
 *        Verfahren nach 
 *        Aho, Hopcroft, Ullman:
 *        Data Structures and Algorithms.
 *        Addison-Wesley (1983), pp. 260
 */


public class Qsort {


    /**
     *  printArray() gibt den Inhalt des Arrays im
     *  vorgegebenen Indexbereich aus.
     *
     *  @author Jan Peleska
     */
    public static void printArray(String msg, int[] a, int i, int j) {

	System.out.println("===============================");
	System.out.println(msg + " i = " + i + " j = " + j);
	System.out.println("===============================");

	for (int k=i; k <= j; k = k + 1 ) {
	    System.out.println("a[" + k + "] = " + a[k]);
	}

    }

    /**
     *  swap() vertauscht 2 Elemente des Arrays <code>a[]</code>
     *
     *  @author Jan Peleska
     */ 
    public static boolean swap(int[] a, int i, int j) {

	int aux = a[i];

	a[i] = a[j];
	a[j] = aux;

	return true;

    }

    /**
     *  findPivotIdx() sucht den Index eines geeigneten
     *  Pivot-Elements
     *
     *  @author Jan Peleska
     *
     *  @param a Array, für den ein Pivotelement ermittelt 
     *           werden soll.
     *  @param i Unterer Index, ab dem das Pivotelement 
     *           gesucht werden soll.
     *  @param j Oberer Index, bis zu dem das Pivotelement 
     *           gesucht werden soll.
     *
     *  @return -1 Falls alle Elemente im Array-Abschnitt 
     *             <code>a[i:j]</code> denselben Wert besitzen.
     *  @return index im Bereich i bis j, so dass 
     *          <code>a[index]</code> nicht das kleinste Element
     *          im Bereich <code>a[i:j]</code> ist.
     *          
     */
    public static int findPivotIdx(int[] a, int i, int j) {

	int pivotValue = a[i];

	for (int k = i; k <= j; k = k + 1) {

	    if ( pivotValue < a[k] ) return k;
	    if ( pivotValue > a[k] ) return i;

	}

	return -1;

    }

    /**
     *  partition() berechnet, an welcher Stelle der
     *  Array-Abschnitt <code>a[i:j]</code> weiter zu partitionieren
     *  ist.
     *
     *  @author Jan Peleska     
     */
    public static int partition(int[] a, 
                                int i, int j, 
                                int pivotValue) {

	int l = i;
	int r = j;

	do {

            
	    while ( a[l] < pivotValue ) l = l + 1;

	    while ( a[r] >= pivotValue ) r = r - 1;

	    System.out.println(" (l,r) = (" + l 
                               + "," + r + ")");

	} while ( l <= r && swap(a,l,r) );

	return l; 
    }

    /**
     *  qsort() ist die Hauptprozedur für das Quicksortverfahren.
     *
     *  @author Jan Peleska
     *
     *  @param a Zu sortierender Array
     *  @param i Untergrenze, einschließlich derer
     *         a im aktuellen qsort() Durchlauf zu sortieren ist.
     *  @param j Obergrenze, einschließlich derer
     *         a im aktuellen qsort() Durchlauf zu sortieren ist.
     */
    public static void qsort(int[] a, int i, int j) {

        // Suche den Index eines geeigneten
        // Pivotelements.
        // Wenn kein gültiges Pivot-Element gefunden wurde,
        // ist pivotIdx == -1. In diesem Fall ist
        // a[] im Bereich a[i:j] bereits sortiert, und
        // die aktuelle Ausführung von qsort() muss nichts tun.        
	int pivotIdx = findPivotIdx(a,i,j);
	int pivotValue = 0;

	if ( pivotIdx >= 0 ) {

	    pivotValue = a[pivotIdx];

	    int partitionIdx = partition(a,i,j,pivotValue);

	    System.out.println("qsort(a," + i + "," + j 
                               + ") pivot: "
			       + pivotValue 
                               + " pivotIdx: " 
                               + pivotIdx);

	    printArray(":",a,i,j);

	    qsort(a,i,partitionIdx-1);
	    qsort(a,partitionIdx,j);

	}

    }


    public static void main(String[] args) {

	int[] a = { 3,1,4,1,5,9,2,6,5,3 };
	int alen = a.length;
	int n1 = 0;
	int n2 = alen - 1;

	printArray("Vor Sortierung:",a,n1,n2);

	qsort(a,n1,n2);

	printArray("Nach Sortierung:",a,n1,n2);



    }

}