import java.util.Random;

/**
 * Klasse quicksort zum sortieren eines Arrays mit dem rekursiven quicksort algorithmus
 * @author Dominic Lehle
 * @version 3.2.08
 */
class Quicksort

{ 
/**
 * gibt ein Array aus
 * @param array das feld das ausgegeben werden soll
 */
  static < T extends Comparable > void feldAusgabe(T array[])
  { 
    System.out.println("Der Array sieht wie folgt aus: ");
    for (int i=0; i<=array.length-1; i++)
    {  System.out.print(array[i]);
       System.out.print(" ");
    }
    System.out.println();
  } 

  /**
   * vertauscht zwei werte in einem Array
   */
  static <T> void vertausche (T array[], int a, int b)
  {  T ablage = array[a];
     array[a] = array[b];
     array[b] = ablage;
  } 
  
  public enum PivotSelection
  {
      erstes,
      mitte,
      letztes, 
      zufall,
      median;
   }
/**
 * Sorts an array in ascending order using the quick sort algorithm.
 * @param array The array to be sorted 
 * @param links = Laufindex bei dem angefangen werden soll 
 * @param rechts = laufindex vom Ende nach rechts ( wegen rekursivem aufruf )
 */
 
static < T extends Comparable > void quicksort(T[] array,int links, int rechts, PivotSelection pivotSelection)
{  
int nachlinks = rechts; 
int nachrechts = links; 
int median;
int mitte= ((links + rechts)/2) ;
T pivot;
 
    
  if (nachrechts - nachlinks >= 1)
      {
          { 
     switch ( pivotSelection )
           {
        case erstes: pivot = array[0];
        break;
        case mitte: pivot = array[mitte];
        break;
        case letztes: pivot = array[rechts];
        break;
        case zufall:
        Random zufall = new Random();
        int k = zufall.nextInt(array.length);
        pivot = array[k];
        break;
        case median: 
        if( array.length % 2 !=0)
        {
           median = (array.length)/2;
        }
           else 
           {
            median = ((array.length/2)+((array.length/2)+1)/2);
           }
           pivot = array[median];
           break;
           default : pivot = array[(nachrechts + nachlinks)/2];
           break;
        }
    }
           
         

         while (nachrechts <= nachlinks)
         {    
              while ((nachrechts < rechts) && (array[nachrechts].compareTo(pivot) <= 0))
                   nachrechts++;

            
              while ((nachlinks > links) && (array[nachlinks].compareTo(pivot) > 0))
                   nachlinks--;

             
              if (nachrechts <= nachlinks)
                   { vertausche(array,nachrechts, nachlinks);
                     nachrechts++;
                     nachlinks--;
                   }
         } 

         
         if (nachlinks > links) 
         {
             nachrechts = links;
             quicksort (array,links, nachlinks ,pivotSelection);

         
         if (nachrechts < rechts) quicksort (array,nachrechts, rechts, pivotSelection);

       }
       else    
        {
                return;                 
        }
}  

 
}
}