/***************************  QuickSort.java  *********************************/

/** rekursives Sortieren mit Quicksort 
 *  Idee: partitioniere die Folge 
 *  in eine elementweise kleinere und eine elementweise groessere Haelfte 
 *  und sortiere diese nach demselben Verfahren
 */

public class QuickSort {
  
  public static void sort (int[] a, int unten, int oben) {   
    int tmp ;
    int i = unten;
    int j = oben;
    int x = a[(unten+oben) / 2];                  // Pivotelement, willkuerlich
  
    do {
        while (a[i] < x) i++;                     // x fungiert als Bremse
        while (a[j] > x) j--;                     // x fungiert als Bremse
        if ( i<=j )  {
            tmp  = a[i];                          // Hilfsspeicher
            a[i] = a[j];                          // a[i] und 
            a[j] = tmp;                           // a[j] werden getauscht
            i++;                  
            j--;  
        }                        
    } while (i <= j); 
                              // alle Elemente der linken Haelfte sind kleiner
                              // als alle Elemente der rechten Haelfte 

    if (unten < j)  sort(a, unten, j);            // sortiere linke Haelfte
    if (i < oben )  sort(a, i, oben );            // sortiere rechte Haelfte
  }

}