/***************************  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) {             // oeffentliche Methode
    quicksort(a, 0, a.length-1);                  // startet private Methode
  }

  private static void quicksort (int[] a, int unten, int oben) {   
    int tmp ;                                     // Hilfsvariable
    int i = unten;                                // untere Intervallgrenze
    int j = oben;                                 // obere Intervallgrenze
    int mitte = (unten + oben) / 2;               // mittlere Position
    int x = a[mitte];                             // Pivotelement
  
    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 Array-Haelfte sind kleiner
                         // als alle Elemente der rechten Array-Haelfte 

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

}