import java.util.*;

public class TaTid2
// b?de mulig ? bruke fra 'main' og via subklasse
{
     Random r = new Random();
     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);
		 return a;
	}

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


     TaTid2(int n, String s)
     {
        int mult = 100000/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  TaTid2  <n>");
	     } else {
		    int n  = new Integer(args[0]).intValue(); // f? parameter fra linja

            new InnStikk(n);
            // new HashSort(n);
            // new QuickSort(n);
		 }
       } // end main


  } // end **** class TaTid2 *****


/* en ny sorteringsklasse , subklasse av TaTid2 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 TaTid2
 */


class InnStikk extends TaTid2{

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

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

  // denne er laget statisk s? den kan kalles fra andre klasser med: InnStikk.innStikk(a,...,...)
  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