public class QuickSortVarianten {
 public static void main(String[] args) {
     
  int size=Integer.parseInt(args[0]);
  String what=args[1];
  int[] testfeld1= new int[size];
  int[] testfeld2= new int[size];
  int[] testfeld3=new int[size];
  int[] ttestfeld1= new int[size];
  int[] ttestfeld2= new int[size];
  int[] ttestfeld3=new int[size];
  
  int[] stestfeld1= new int[size];
  int[] stestfeld2= new int[size];
  int[] stestfeld3= new int[size];
  int[] rtestfeld1= new int[size];
  int[] rtestfeld2= new int[size];
  int[] rtestfeld3= new int[size];
  
  for (int i = 0; i<size; i++) {
     int num = (int)(Math.random()*Integer.MAX_VALUE);
     testfeld1[i] = num;
     testfeld2[i] = num;
     testfeld3[i] = num;
        }
  for (int i = 0; i<size; i++) {
     int num = (int)(Math.random()*10);
     ttestfeld1[i] = num;
     ttestfeld2[i] = num;
     ttestfeld3[i] = num;
        }
  for (int i = 0; i<size; i++) {
     stestfeld1[i] = i;
     stestfeld2[i] = i;
     stestfeld3[i] = i;
        }
  for (int i = 0; i<size; i++) {
     rtestfeld1[i] = size-i;
     rtestfeld2[i] = size-i;
     rtestfeld3[i] = size-i;
 }
        
          
  if (what.equals("zufaellig")) {      
  long t1 = System.currentTimeMillis();
  quicksort(testfeld1);
  long t2 = System.currentTimeMillis();
  quicksort3(testfeld2);
  long t3 = System.currentTimeMillis();
  quicksort3opt(testfeld3);
  long t4 = System.currentTimeMillis();
  System.out.println("Eingabe zufaellig, qsort                                       :" + (t2 - t1));
  System.out.println("Eingabe zufaellig, qsort3                                      :" + (t3 - t2));
  System.out.println("Eingabe zufaellig, qsort3, kleine mit insertionSort            :" + (t4 - t3));
  }
  
  if (what.equals("aufsteigend")) {      
  long st1 = System.currentTimeMillis();
  quicksort(stestfeld1);
  long st2 = System.currentTimeMillis();
  quicksort3(stestfeld2);
  long st3 = System.currentTimeMillis();
  quicksort3opt(stestfeld3);
  long st4 = System.currentTimeMillis();
  System.out.println("Eingabe aufsteigend sortiert, qsort                            :" + (st2 - st1));
  System.out.println("Eingabe aufsteigend sortiert, qsort3                           :" + (st3 - st2));
  System.out.println("Eingabe aufsteigend sortiert, qsort3, kleine mit insertionSort :" + (st4 - st3));
  } 

  if (what.equals("absteigend")) {      
  long rt1 = System.currentTimeMillis();
  quicksort(rtestfeld1);
  long rt2 = System.currentTimeMillis();
  quicksort3(rtestfeld2);
  long rt3 = System.currentTimeMillis();
  quicksort3opt(rtestfeld3);
  long rt4 = System.currentTimeMillis();
  System.out.println("Eingabe absteigend sortiert, qsort                             :" + (rt2 - rt1));
  System.out.println("Eingabe absteigend sortiert, qsort3                            :" + (rt3 - rt2));
  System.out.println("Eingabe absteigend sortiert, qsort3, kleine mit insertionSort  :" + (rt4 - rt3));
  }
  if (what.equals("wenige")) {      
  long tt1 = System.currentTimeMillis();
  quicksort(ttestfeld1);
  long tt2 = System.currentTimeMillis();
  quicksort3(ttestfeld2);
  long tt3 = System.currentTimeMillis();
  quicksort3opt(ttestfeld3);
  long tt4 = System.currentTimeMillis();
  System.out.println("Eingabe zufaellig, nur 10 , qsort                           :" + (tt2 - tt1));
  System.out.println("Eingabe zufaellig, nur 10 ,qsort3                           :" + (tt3 - tt2));
  System.out.println("Eingabe zufaellig, nur 10 ,qsort3, kleine mit insertionSort :" + (tt4 - tt3));
  }
 /* 
  */

}

 
 public static void check(int[] arr) {
   printArray(arr);
   quicksort(arr);
   printArray(arr);
   System.out.println(isSorted(arr));
   if (!isSorted(arr)) {System.out.println(1/0);}
 }
 public static void check3(int[] arr) {
   printArray(arr);
   quicksort3(arr);
   printArray(arr);
   System.out.println(isSorted(arr));
   if (!isSorted(arr)) {System.out.println(1/0);}
 }
 public static boolean isSorted(int[] arr) {
  boolean result = true;
  for (int i = 1; i < arr.length; i++) {
    result = result && (arr[i-1] <= arr[i]);
    }
return result;
}
  
 
 public static void printArray(int[] arr) {
      for (int i=0; i < arr.length; i++) {
         System.out.print(arr[i] + " ");
      }
      System.out.println();
 }

public static void swap(int[] arr, int l, int r) {
  int tmp = arr[l];
  arr[l] = arr[r];
  arr[r] = tmp;
}
public static int partition(int[] arr, int left, int right, int pivot) {
  // in-place partition, geht davon aus, dass pivot sich an arr[left] befindet
  int l = left+1; // fange links neben dem Pivot an
  int r = right;  // fange rechts ganz rechts an
  boolean proceed = true; // vertausche weiter?
  while (proceed) {
   while (l <= right  && arr[l] < pivot) {l++;} // schiebe l nach links bis ein zu gro"sses Element gefunden
   while (r >= left &&  arr[r] > pivot) {r--;} // schiebe r nach rechts bis ein zu kleines Element gefunden
   if (l < r) {
      swap(arr,l,r); // vertausche arr[l] und arr[r]
      l++;           // schiebe l nach links und r nach rechts
      r--;
    } 
    else {proceed = false;} //stoppe
  }
  // setze Pivot an die richtige Position
  swap(arr,left,r); // r ist das erste zu kleine Element von rechts
  return r;
} 
 public static void quicksort(int[] arr) {
  // sortiere alle Elemente des Arrays:
  qsort(arr, 0, arr.length-1);
  }
 public static void quicksort3(int[] arr) {
  // sortiere alle Elemente des Arrays:
  qsort3(arr, 0, arr.length-1);
  }
 public static void quicksort3opt(int[] arr) {
  // sortiere alle Elemente des Arrays:
  qsort3opt(arr, 0, arr.length-1);
  }
public static void qsort(int[] arr, int left, int right) {
 // sortiere den Tellbereich von left bis right im Array arr
 if (left < right) { // mehr als ein Element zu sortieren 
 // w"ahle erstes Element als Pivot
 int pivot = arr[left];
 // partioniere anhand des Pivot-Elements 
 int pivotIndex = partition(arr,left,right,pivot);
 // sortiere linken und rechten Teil rekursiv
 qsort(arr,left,pivotIndex-1);
 qsort(arr,pivotIndex+1,right);
 
}
}

public static void qsort3(int[] arr, int left, int right) {
 // sortiere den Tellbereich von left bis right im Array arr
 if (left < right) { // mehr als ein Element zu sortieren 
 // w"ahle median von  drei Elementen als Pivot
 int index1 = left;
 int index2 = right;
 int index3 = (left+right)/2;
 int medIndex = index1;
 if (arr[index1] <= arr[index2] && arr[index2] <=  arr[index3])  {medIndex = index2;}
 if (arr[index3] <= arr[index2] && arr[index2] <=  arr[index1])  {medIndex = index2;}
 if (arr[index1] <= arr[index3] && arr[index3] <=  arr[index2])  {medIndex = index3;}
 if (arr[index2] <= arr[index3] && arr[index3] <=  arr[index1])  {medIndex = index3;}
 swap(arr,left,medIndex);
  int pivot = arr[left];
 // partioniere anhand des Pivot-Elements 
 int pivotIndex = partition(arr,left,right,pivot);
 // sortiere linken und rechten Teil rekursiv
 qsort3(arr,left,pivotIndex-1);
 qsort3(arr,pivotIndex+1,right);

}
}

public static void insertionSort(int[] a,int left,int right) {
  for (int i = left; i <= right ; i++) {
    int toInsert = a[i];  // einzufuegendes Element
    int j = i;
      
    while (j > 0 && a[j-1] > toInsert) {
     a[j] = a[j-1]; // schiebe a[j-1] um 1 nach rechts
     j--;
    }
    a[j] = toInsert; // einfuege Position gefunden
    }
}

public static void qsort3opt(int[] arr, int left, int right) {
 // sortiere den Tellbereich von left bis right im Array arr
 if (left < right) { // mehr als ein Element zu sortieren 
  if (right - left  < 10) {insertionSort(arr,left,right);} 
  else {
 // w"ahle median von  drei Elementen als Pivot
     int index1 = left;
     int index2 = right;
     int index3 = (left+right)/2;
     int medIndex = index1;
     if (arr[index1] <= arr[index2] && arr[index2] <=  arr[index3])  {medIndex = index2;}
     if (arr[index3] <= arr[index2] && arr[index2] <=  arr[index1])  {medIndex = index2;}
     if (arr[index1] <= arr[index3] && arr[index3] <=  arr[index2])  {medIndex = index3;}
     if (arr[index2] <= arr[index3] && arr[index3] <=  arr[index1])  {medIndex = index3;}
     swap(arr,left,medIndex);
      int pivot = arr[left];
     // partioniere anhand des Pivot-Elements 
     int pivotIndex = partition(arr,left,right,pivot);
     // sortiere linken und rechten Teil rekursiv
     qsort3opt(arr,left,pivotIndex-1);
     qsort3opt(arr,pivotIndex+1,right);

  }
}

}

}