import java.util.*;
import easyIO.*;

public class TaTid
// b?de mulig ? bruke fra 'main' og via subklasse
{
     Random r = new Random();
     //Out tast = new Out()
     int [] a ;

     int [] lagOgFyll(int n) {
		 // lager en arayy a med tilfeldig innhold
		 int [] a = new int [n];
		 for (int i=0; i < n ; i++)
		 	a[i]=  r.nextInt(n);

		// a[0] = 10000000;
		 return a;
	}

   static void print(String s, int [] a,  int i, int num) {
	   int j = (i/10)*10;
	   System.out.println(s);
	   System.out.print("\n"+i+" |");
		 for (int k = j; k< num; k++) {
			   System.out.print(a[k]+ " ");
			   if (( (k+1) % 10) == 0 ){
				   System.out.println("");
				   System.out.print(i+" |");
			   }
	     }
	     System.out.println("\n");
   } // end print


   void testSortert(int [] a) {
		for(int i = 0; i< a.length-1; i++)
		  if(a[i] >a[i+1]) {
			  print ("FEIL", a, i, 30);
			  System.out.println(" FEIL: a[" + i +"] > a[" +(i+1) +"]");
			  System.exit(0);
		  }
	  }


     TaTid(int n, String s)
     {
        int mult = 10000000/n;
        mult = Math.max(1,mult);

        double akkumTid =0,tid =0;

        // if n is too small, repeat loop
        for ( int i = 1; i <= mult; i++) {
			a = lagOgFyll(n);
			tid = System.currentTimeMillis();
              bruk(n);
            akkumTid += System.currentTimeMillis() - tid;
            testSortert(a);
	    }
        akkumTid =  akkumTid *1.0/mult;
        System.out.println(s + ",: " + akkumTid + " millisekunder,n = " +n);
     }

      void bruk(int n)
      { // redefineres i subklasse
      } // end bruk

      public static void  main ( String[] args)
      {  if (args.length < 1){ System.out.println(" Bruk: \n >java  TaTid  <n>");
	     } else {
		    int n  = new Integer(args[0]).intValue(); // f? parameter fra linja

           for (int i = n/10; i <= n; i +=n/10) {
				new InnStikk(i);
			  //  new HashSort(i);
				new QuickSort(i);
				new JavaSort(i);
				new Shell2(i);
				System.out.println("");
		   }
		 }
       } // end main


  } // end **** class Tatid *****


/* en ny sorteringsklasse lages ved ? lage:
  a) en versjon av bruk som kaller sorteringsmetoden
  b) en kontruktor som sier {super(n,"NAVNET p? metoden");}
  c) et kall fra 'main' i TaTid
 */


class InnStikk extends TaTid{

 void bruk (int n)	{
	 innStikk(a,0,n-1);
  }

  InnStikk(int n) { super(n,"Innstikk-sortering ");}

   static void innStikk(int [] a, int l, int r ) {
	if (l < r ) {
       // at least two elements
       int i, t;

       for (int k = l ; k < r; k++) {
       	 if (a[k] > a[k+1]) {
       	   t = a[k+1];
  	   	   i = k;

  	   	   do{ //  g? bakover, skyv de andre
       	        //  og finn riktig plass for ?t?
       	       a[i+1] = a[i];
  	   	       i--;
  	   		} while (i >= l  &&  a[i] > t);

   	        a[i+1] = t;
  	   	 }
       } // end k
      }
   } // end innStikk

} // end class InnStikk


class JavaSort extends TaTid{

 void bruk (int n)	{
	 javaSort(a,0,n);
  }

  JavaSort(int n) { super(n,"Java    -sortering ");}

  static void javaSort(int [] a, int l, int r ) {
	if (l < r ) {
       Arrays.sort(a,l,r);
       } // end k

   } // end javaSort

} // end class JavaSort

class HashSort extends TaTid {

 void bruk (int n)	{
	 hashSort(a,0,n-1);
  }

  HashSort(int n) { super(n,"HashSort-sortering ");}

   void hashSort(int [] a, int l, int r ) {
       int [] b = new int [a.length];
       int max =0, n =a.length, acumVal =0, j ;

       // finn max
       for (int i = 0; i<n; i++)
         if (a[i] > max) max = a[i];

       int gruppeSt?rrelse = (max+1)/((int)(0.1*n));
      // System.out.println(" grSt:"+gruppeSt?rrelse + ", n/grSt: " +
      //                    (max/gruppeSt?rrelse));
       int [] ant = new int[max/gruppeSt?rrelse +1];

       // tell opp hvor mange av hver
       for (int i = 0; i<n; i++)
			ant[a[i] /gruppeSt?rrelse] ++;
		//	 print ("A ant: - antall", ant, 0, ant.length);

		// lag pekere
		for (int i = 0; i < ant.length; i++)  {
          j = ant[i];
          ant[i] = acumVal;
          acumVal += j;
        }
       //  print ("B ant: - pekere", ant, 0, ant.length);

        // flytt  tallene i sortert (p? dette feltet) til til.
	    for (int i = 0; i < n; i++)
		      b [ant[a[i] /gruppeSt?rrelse]++ ] = a[i];

		//  print ("C b: - gruppe-sortert", b, 0, b.length);

		// sorter med innstikk-sortering, f?rste spesielt
		InnStikk.innStikk(b,0,ant[0]);
		for (int i = 1; i < ant.length; i++)
		   InnStikk.innStikk(b,ant[i-1],ant[i]-1);
	 // print ("D b: - hel-sortert", b, 0, b.length);


		// kopier tilbake
		for (int i = 0; i < a.length; i++)
		  a[i] = b[i];

   } // end hashSort



} // end class HashSort


class QuickSort extends TaTid{

 void bruk (int n)	{
	 quickSort(a,0,n-1);
  }

  QuickSort(int n) { super(n,"QuickSort-sortering");}


    void  quickSort ( int [] a,int l,int r) {
        int i=l, j=r;
        int t, part = a[(l+r)/2];

          while ( i <= j) {
             while (a[i] < part ) i++;
             while (part < a[j] ) j--;

             if (i <= j) {
                 t    = a[j];
                 a[j]= a[i];
                 a[i]= t;
                 i++;
                  j--;
             }
           }

           if ( l < j ) {
		       if ( j-l < 20)
		         InnStikk.innStikk (a,l,j);
		       else
		         quickSort (a,l,j);
		    }
		   if ( i < r ) {
		       if ( r-i < 20)
		          InnStikk.innStikk (a,i,r);
		        else
		          quickSort (a,i,r);
		   }


    } // end quickSort


} // end class QuickSort

class Shell2 extends TaTid{

 void bruk (int n)	{
	 shellSort(a);
  }

  Shell2(int n) { super(n,"Shell2  - sortering");}

   void shellSort(int [] a)
   {  int n = a.length;
	  int [] gapVal  = {1,2,5,11,23,47,101};
	  int gap ;

      for (int gapInd = gapVal.length -1; gapInd >= 0; gapInd --) {
		   gap = gapVal[gapInd];
		  for (int i = gap ; i < a.length ; i++)
		   // for (int i = gap ; i < a.length ; i+=gap)
			 if (a[i] < a[i-gap] ) {
				int tmp = a[i],
					  j = i;
				 do
				 {  a[j] = a[j-gap];
					 j = j- gap;
				 }  while (j >= gap && a[j-gap] > tmp);

				 a[j] = tmp;
			}
	 }
 } // end



} // end class Shell2Sort