/**
 * Quicksort.java
 *
 * @author Markus Dahlweid
 * @version $id$
 */

public class Quicksort  {
    
    public static int[] Folge;

    /**
     * Initialisiere das Array Folge mit zehn beliebigen Werten.
     */
    public static void initFolge() {
	Folge = new int[] {
	    36, 2, 49, 5, 18, 16, 42, 9, 57, 5
	};
    }

    /**
     * Die Funktion <code>printArray</code> gibt die Elemente des
     * Arrays Folge in den Grenzen UntereGrenze und ObereGrenze aus.
     *
     * @param UntereGrenze Die untere Grenze des auszugebenen
     * Bereichs des Arrays Folge.
     * @param ObereGrenze  Die obere Grenze des auszugebenen
     * Bereichs des Arrays Folge.
     * @param Folge Das zu sortierende Array.
     */
    public static void printArray (int UntereGrenze,
				   int ObereGrenze,
				   int[] Folge) {
	
	System.out.print("Folge[" + UntereGrenze + ".." 
			 + ObereGrenze + "] = [ ");
	for (int i=UntereGrenze; i<=ObereGrenze; i++) {
	    System.out.print(Folge[i]);
	    if (i != ObereGrenze) {
		System.out.print(", ");
	    }
	}
	
	System.out.println("]");
    }

    /**
     * Die Funktion <code>quicksort</code> sortiert die Elemente 
     * des Arrays Folge in den Grenzen UntereGrenze und ObereGrenze
     * nach dem Quicksort Algorithmus
     *
     * @param UntereGrenze Die untere Grenze des zu sortierenden
     * Bereichs des Arrays Folge.
     * @param ObereGrenze  Die obere Grenze des zu sortierenden
     * Bereichs des Arrays Folge.
     * @param Folge Das zu sortierende Array.
     */
    public static void quicksort (int UntereGrenze,
				  int ObereGrenze,
				  int[] Folge) {
	int links = UntereGrenze;
	int rechts = ObereGrenze;
	int Pivotelement = Folge[((UntereGrenze+ObereGrenze) / 2)];

	printArray(UntereGrenze, ObereGrenze, Folge);
	
	do {
	    while ( Folge[links] < Pivotelement ) {
		links = links + 1;
	    }
	    while ( Pivotelement < Folge[rechts] ) {
		rechts = rechts - 1;
	    }

	    if (links <= rechts) {
		// Vertauschen der Elemente
		int Merke = Folge[links];
		Folge[links] = Folge[rechts];
		Folge[rechts] = Merke;

		links = links + 1;
		rechts = rechts - 1;
	    }
	} while ( links <= rechts );

	// Rekursion
	if ( UntereGrenze < rechts ) {
	    quicksort ( UntereGrenze, rechts, Folge );
	}

	if ( links < ObereGrenze ) {
	    quicksort ( links, ObereGrenze, Folge ); 
	}
    }

    //---------------------------------------------------------------
    public static void main(String[] args) {

	initFolge();

	quicksort(0, 9, Folge);
	printArray(0, 9, Folge);
    }

}