class myRandom{
    java.util.Random random = new java.util.Random(42);
    int rand (){
        return Math.abs(random.nextInt());
        }
    }
    
    

class ArrayGen{
    int dim = 1000;
    int [] master;
    
    ArrayGen(int d){
        dim = d;
        myRandom rand = new myRandom();
        master = new int [d];
        for (int i=0; i < d; i++) master[i] = rand.rand();
    }
    
    
    int[] arrayKopie(){
        int[] kopie = new int [dim];
        // for (int i=0; i < dim; i++) kopie[i] = master[i];
        System.arraycopy(master, 0, kopie, 0, dim);
        return kopie;
    }
 }

class TestIntSort{
    
    static boolean testSort(int [] a){
       int Hi = a.length-1;
       for (int k = 0; k < Hi; k++)
         if (a[k+1] < a[k]) return false;
       return true;  
       }

    final static int anzahl = 10000000;

    public static void main(String args[]) {
     ArrayGen ag = new ArrayGen(anzahl);   
     int [] feld;
     long zeitVor, zeitMitte, zeitNach;
     long zeitX1, zeitX2;
     long zeit1, zeit2, zeit3, zeit4;
     EinAus.initAusgabe("Protokoll1");
     System.out.println("Sortierprogramme für Integer");
     System.out.println("Anzahl der Feldelemente: " + anzahl);
     EinAus.writeLnP("Anzahl der Feldelemente: " + anzahl);

     /*
     System.out.print("Bubble Sort1:   ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.bubbleSort1(feld);
     zeitMitte = System.nanoTime();
     IntSorter.bubbleSort1(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit BubbleSort1: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit BubbleSort1: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");


     System.out.print("Bubble Sort2:   ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.bubbleSort2(feld);
     zeitMitte = System.nanoTime();
     IntSorter.bubbleSort2(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit BubbleSort2: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit BubbleSort2: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");
     
     System.out.print("Bubble Sort3:   ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.bubbleSort3(feld);
     zeitMitte = System.nanoTime();
     IntSorter.bubbleSort3(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit BubbleSort3: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit BubbleSort3: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");


     System.out.print("Selection Sort: ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.selectionSort(feld);
     zeitMitte = System.nanoTime();
     IntSorter.selectionSort(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit SelectionSort: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit SelectionSort: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");


     System.out.print("Insertion Sort: ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.insertionSort(feld);
     zeitMitte = System.nanoTime();
     IntSorter.insertionSort(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit InsertionSort: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit InsertionSort: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");
   
     /**/
     System.out.print("Shell Sort: ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.shellSort(feld);
     zeitMitte = System.nanoTime();
     IntSorter.shellSort(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit ShellSort: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit ShellSort: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");
     
     System.out.print("Quick Sort: ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.quickSort(feld);
     zeitMitte = System.nanoTime();
     IntSorter.quickSort(feld);
     zeitNach = System.nanoTime();
     IntSorter.bubbleSort2(feld);
     zeitX1 = System.nanoTime();
     IntSorter.insertionSort(feld);
     zeitX2 = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     zeit3 = (zeitX1 - zeitNach)/1000000;
     zeit4 = (zeitX2 - zeitX1)/1000000;
     System.out.println("Laufzeit QuickSort: "+zeit1+" vorsortiert: "+ zeit2);
     System.out.println("Laufzeit BubbleSort vorsortiert: "+ zeit3);
     System.out.println("Laufzeit InsertionSort vorsortiert: "+ zeit4);
     EinAus.writeLnP("Laufzeit QuickSort: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit BubbleSort vorsortiert: "+ zeit3);
     EinAus.writeLnP("Laufzeit InsertionSort vorsortiert: "+ zeit4);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");
     
     System.out.print("Quick Sort2:");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.quickSort2(feld);
     zeitMitte = System.nanoTime();
     IntSorter.quickSort2(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit QuickSort2: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit QuickSort2: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");
     
     System.out.print("Merge Sort: ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.mergeSort(feld);
     zeitMitte = System.nanoTime();
     IntSorter.mergeSort(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit MergeSort: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit MergeSort: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");

     System.out.print("Heap Sort: ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.heapSort(feld);
     zeitMitte = System.nanoTime();
     IntSorter.heapSort(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit HeapSort: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit HeapSort: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");
     
     System.out.print("Distribution Sort: ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     IntSorter.distributionSort(feld);
     zeitMitte = System.nanoTime();
     IntSorter.distributionSort(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit DistributionSort: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit DistributionSort: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");
     
     System.out.print("Java Sort: ");
     feld = ag.arrayKopie();
     zeitVor = System.nanoTime();
     java.util.Arrays.sort(feld);
     zeitMitte = System.nanoTime();
     java.util.Arrays.sort(feld);
     zeitNach = System.nanoTime();
     zeit1 = (zeitMitte -zeitVor)/1000000;
     zeit2 = (zeitNach - zeitMitte)/1000000;
     System.out.println("Laufzeit JavaSort: "+zeit1+" vorsortiert: "+ zeit2);
     EinAus.writeLnP("Laufzeit JavaSort: "+zeit1+" vorsortiert: "+ zeit2);
     if (!testSort(feld)) System.out.println("Fehler !!!! Nix ist sortiert !!!!");
     
     /**/

     EinAus.endeAusgabe();
     System.out.println("");
    
    }
}