//fil: SortProg.java til INF1020 - h2005 -  Arne Maus, Ifi, Univ. of Oslo
import java.io.*;
import java.util.*;
import easyIO.*;



// --------------( SortTid ) ------------------------------
class SortTid {

  int n, iterNum;
  static final long totNum= 50000000;
  long startTid, sluttTid;
  double  tidBrukt;
   int [] a, aOrig ;  // arrray som skal sortet
  String alg;


  SortTid(int num, String algt)
   { // Konstruktor: initier n og a med tilfeldige tall
     n = num;
     iterNum = (int) totNum /n;
     a = new int [n];
     aOrig = new int [n];
     alg = algt;
     Random r = new Random( 123789+n);

     for(int i = 0 ; i < n; i++)
       aOrig[i] = Math.abs(r.nextInt())% n;
   }

  void taTid()
  {  startTid = System.currentTimeMillis();
     for ( int j = 0; j < iterNum ; j++)
      { for (int i = 0; i < n; i++)
           a [i] = aOrig[i];
        sorter();
      }
     sluttTid =System.currentTimeMillis();
     sjekkSortering();
     tidBrukt =  ((double)(sluttTid - startTid))/iterNum;
     System.out.println("Tid brukt av "+ alg + "=" + Format.align(tidBrukt,10,4) + " millisek");
  }

  void sorter ()
  { // standard Bruk ikke def - byttes ut i subklasse

  }

  void sjekkSortering ()
  // ----------------------------------------------
  // sjekk sortering, print hvis feil
  //----------------------------------------------
  { int i, numerr =0, firsterr = -1, num =n;
    if(n > 100) num= 100;

    for (i = 1; i < n; i++ )
    if ( a[i-1] > a[i] )
    { numerr++;
      if (firsterr <0) firsterr = i;
    }

    if (firsterr >= 0 && numerr < 2000)
    { System.out.println(" **" + alg + "- FEIL: f?rst oppdaget"+
                             firsterr + "  ant feil : " + numerr);
      if (firsterr<100) printn( 0,num);else printn(firsterr-10,num );
     }
    }// end sjekkSortering


     void printn(int start, int num2 )
      //------------------------------------------------
      // Print num2 tall i a,  10 per  linje
      //*------------------------------------------------*/
     { int i;

       System.out.print(Format.align(start,4)+" |");
       for (i = 0; i< num2; i++)
       { System.out.print(Format.align(a[i+start],4));
         if (( (i+1) % 10) == 0 && (i+1) < num2)
       { System.out.println("");
             System.out.print( Format.align((start+i+1),4)+" |");
         }
        }
        System.out.println("");
     }// end printn

} // end class SortTid

// ------------( SortProg ) ---------------------------

public class SortProg{

  public static void main (String [] args)
  { if (args.length < 1)
      System.out.println(" Riktig bruk: >java SortProg  n");
    else {
      new QuickTid  (Integer.parseInt(args[0])).taTid();

      new QuickIn115 (Integer.parseInt(args[0])).taTid();

      new TreeTid  (Integer.parseInt(args[0]), "Tree  - sort:").taTid();

      new HeapSortTid(Integer.parseInt(args[0])).taTid();

      new TelleSortTid(Integer.parseInt(args[0])).taTid();

      new BucketSortTid(Integer.parseInt(args[0])).taTid();

      new RadixSortTid(Integer.parseInt(args[0])).taTid();

  //    new InsertTid (Integer.parseInt(args[0])).taTid();

//      new BobleTid (Integer.parseInt(args[0])).taTid();

       new ShellTid (Integer.parseInt(args[0])).taTid();

    // new ShellBobleTid (Integer.parseInt(args[0])).taTid();

       new ShellTreeTid (Integer.parseInt(args[0])).taTid();

    }
  } // end main
} // end


// ---------------------( QuickTid  )------------------------------------

class QuickTid extends SortTid
{
  QuickTid(int n)
  { super(n, "Quick - sort:");
  }

  void sorter()
  { // quicksort
    quicksort ( a,0,n-1);
  }

   void  quicksort ( int [] a,int l,int r)
  // partitions arraysegment a[l,r] in 'small' and 'big'
  { 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 < 10) innstikkSort (a,l,j); else quicksort (a,l,j);}
      if ( i < r )
        {if ( r-i < 10) innstikkSort (a,i,r); else quicksort (a,i,r); }


    }/* end quicksort */

   void innstikkSort(int a[],int l, int r)
   {int i, t;

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

         while (i >= 0 && a[i] > t)
         { a[i+1] = a[i]; i--;}

         a[i+1] = t;
    }
    }

} // end QuickTid

// ---------------------( QuickIn115  )------------------------------------

class QuickIn115 extends SortTid
{
  QuickIn115(int n)
  { super(n, "In115 q-sort:");
  }

  void sorter()
  { // quicksort
    quickSort ( a,0,a.length - 1);
  }

   void  quickSort ( int [] a,int l,int r)
  // partitions arraysegment a[l,r] in 'small', 'equal' and 'big'
  { int s = l-1, like = 0, ind;
    int t, part = a[(l+r)/2];

    for ( int b = l; b <= r; b++)
       if ( a[b] == part )
       {  like++;
          t = a[s+like];
          a[s+like] = a[b];
          a[b] = t;
       } else
       if (a[b] < part)
       {  s++;
          ind = s+like;
          t = a[b];
          a[b] = a[ind];
          a[ind]= a[s];
          a[s] = t;
        }

     if ( l < s )         quickSort (a,l,s);
     if ( s+1+like < r )  quickSort (a,s+1+like,r);

   }/* end quickSort */

} // end QuickIn115

// ---------------------( TreeTid )---------------------------------------

class TreeTid extends SortTid
{
  TreeTid(int n, String s)
  { super(n, s); }

  void sorter()
  { treeSort ( a); }

   void dyttNed (int i, int n)
  // Rota er (muligens) feilplassert - dytt gammel nedover
  // f? ny st?rre oppover
  { int j = 2*i+1, temp = a[i];
    while(j <= n )
    { if ( j < n && a[j+1] > a[j] ) j++;
      if (a[j] > temp)
      { a[i] = a[j]; i = j; j = j*2+1;}
      else break;
    }
    a[i] = temp;
  } // end dyttOpp

   void bytt (int k, int m)
  { int temp = a[k];
     a[k] = a[m];
     a[m] = temp;
  }

   void treeSort( int [] a)
  { int n = a.length-1;
    for (int k = n/2 -1; k > 0 ; k--) dyttNed(k,n);
    for (int k = n ; k > 0 ; k--)
    { dyttNed(0,k); bytt (0,k); }
  }

} // end TreeTid

// ----------------(HeapSortTid ) -----------------------

class HeapSortTid extends TreeTid
{
  HeapSortTid(int n)
  { super(n, "Heap  - sort:");}

  void sorter()
  { heapSort (a);}

   void dyttOpp(int i)
  // Bladnoden p? plass i er (muligens) feilplassert
  // Dytt den oppover mot rota
  { int j = (i-1)/2, temp = a[i];

    while( temp  > a[j] && i > 0 )
    { a[i] = a[j]; i = j; j = (i-1)/2; }

    a[i] = temp;
  } // end siftDown

   void heapSort( int [] a)
  { int n = a.length -1;
    for (int k = 1; k <= n ; k++) dyttOpp(k);
    bytt(0,n);
    for (int k = n-1; k > 0 ; k--)
    { dyttNed(0,k); bytt (0,k); }
  }

} // end HeapSortTid

// ------------------------( TelleSort )---------------------------
class TelleSortTid extends SortTid
{
  TelleSortTid(int n)
  { super(n, "telle - sort:");
  }

  void sorter()
  { // telleSort
     telleSort( a, n );
  }

  void telleSort ( int [] a , int max)
  // assumes max known
  {   int [] ant = new int [max+1];
      int ind = 0;

      for (int i = 0; i < n; i++)
        ant[a[i]]++;

      // lag tallene
      for (int i = 0; i <= n; i++)
        for (int j = ant[i]; j > 0 ; j--)
          a[ind++] = i;

    }/* end telleSort */
}

// ------------------------( RadixSort )---------------------------
class RadixSortTid extends SortTid
{ int [] b, c;
  final static int numBit = 10, rMax = 1024-1;

  RadixSortTid(int n)
  { super(n, "radix - sort:");
    b = new int [n];
  }

  void sorter()
  { // radixSort
     int max = 0;

     for (int i = 0 ; i < a.length; i++)
      if (a[i] > max) max = a[i];

      c = radixSort( a,b, 0, max);

      if ( a != c)
         for (int i = 0; i < n; i++)
             a[i] = c[i];
  }

  int [] radixSort ( int [] fra, int [] til , int bit, int max )
  // assumes max known
  {   int [] ant = new int [rMax+1];
      int  acumVal = 0, j;

      for (int i = 0; i < n; i++)
        ant[((fra[i]>> bit) & rMax)]++;

      // Add up in 'ant' - acumulated values
      for (int i = 0; i <= rMax; i++)
      { j = ant[i];
        ant[i] = acumVal;
        acumVal += j;
      }

      // flytt  tallene
      for (int i = 0; i < n; i++)
          til[ant[((fra[i]>>bit) & rMax)]++] = fra[i];

       if ( (1 << (bit + numBit)) < max )
           return radixSort ( til, fra, bit + numBit, max);
      else return til;

    }/* end radixSort */
}
// ------------------------( B?tteSort )---------------------------
class BucketSortTid extends SortTid
{
  BNode s, v;

  class BNode
  { BNode neste; int verdi;
    BNode (BNode n, int v)
    { neste =n; verdi =v; }
   }

  BucketSortTid(int n)
  { super(n, "b?tte - sort:");
     for(int i = 0; i<n; i++)
     s = new BNode( s, a[i]);
   }

  void sorter()
  { // b?tteSort

    s = bucketSort( s, a.length );

  }

  void sjekkSortering()
  {   v = s;
      int ind = 0;

      for (int i = 0 ; i < n; i++)
      { a[ind++] = v.verdi; v = v.neste;}

      super.sjekkSortering();
  }

  BNode bucketSort ( BNode s , int max)
  // assumes max known
  {   BNode [] list = new BNode [max+1];
      BNode t;

       for (int i = 0; i < max; i++)
        { t = s;
          s = s.neste;
          t.neste = list[t.verdi];
          list[t.verdi] = t;
         }

      // lag liste FIFO from LIFO +LIFO
      for (int i = max; i >= 0; i--)
       while (list[i] != null )
       { t = list[i];
         list[i] = t.neste;
         t.neste = s;
         s = t;
       }

       return s;

    }/* end bucketSort */
}

// ------------------------( InsertTid )--------------------------------

class InsertTid extends SortTid
{
  InsertTid(int n)
  { super(n, "Insert -sort:"); }

  void sorter()
  { insertSort(0,a.length-1);}

   void insertSort(int l, int r)
   {int i, t;

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

         while (i >= 0 && a[i] > t)
         { a[i+1] = a[i]; i--;}

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

}


// ------------------------( BobleTid )--------------------------------

class BobleTid extends SortTid
{
  BobleTid(int n)
  { super(n, "Boble  -sort:"); }

  void sorter()
  { bobleSort(a);}

  void bytt(int[] a, int i, int j)
     { int t = a[i];
        a[i]=a[j];
        a[j] = t;
   }


   void bobleSort (int [] a)
   {int i = 0, max = a.length-1;

      while ( i < max )
        if (a[i] > a[i+1])
        {     bytt (a, i, i+1);
               if (i > 0 )  i = i-1;
        } else {
               i = i + 1;
        }
   } // end bobleSort


}

// ------------------------( ShellTid )--------------------------------

class ShellTid extends SortTid
{
  ShellTid(int n)
  { super(n, "Shell  -sort:"); }

  void sorter()
  { shellSort(a);}

   void shellSort(int [] a)
   {
       for (int gap = a.length/2 ; gap > 0 ; gap =gap/2) {
           for (int i = gap ; i < a.length ; i++)
             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 shell2Sort

}

// ------------------------( ShellBobleTid )--------------------------------

class ShellBobleTid extends SortTid
{
  ShellBobleTid(int n)
  { super(n, "SBoble -sort:"); }

  void sorter()
  { shellBobleSort(a);}

  void bytt(int[] a, int i, int j)
     { int t = a[i];
        a[i]=a[j];
        a[j] = t;
   }


   void shellBobleSort(int [] a)
   {
      for (int gap = a.length/2 ; gap > 0 ; gap =gap/2) {
              int i = gap, gap2 = 2*gap;

               while ( i < a.length )
                     if (a[i-gap] > a[i])
                     {     bytt (a, i - gap, i);
                            if (i >= gap2 )  i = i-gap;
                     } else { i += gap; }

       } // end for
    } // end shellBobleSort

}

// ------------------------( ShellTreeTid )--------------------------------

class ShellTreeTid extends SortTid
{
  ShellTreeTid(int n)
  { super(n, "STree  -sort:"); }

  void sorter()
  { shellTreeSort(a);}

    void dyttNed (int i, int n, int gap)
    // Rota i er (muligens) feilplassert - dytt gammel nedover
    // f? ny st?rre oppover
    { int j = (gap+1)*i+1, temp = a[i];
      while(j>=0 && j<= n )
      { if (j+gap <= n && a[j+gap] > a[j] ) j+=gap;
        if (a[j] > temp)
        { a[i] = a[j]; i = j; j = j*(gap+1)+gap;}
        else break;
      }
      a[i] = temp;
    } // end dyttOpp

     void bytt (int k, int m)
    { int temp = a[k];
       a[k] = a[m];
       a[m] = temp;
    }


   void shellTreeSort(int [] a)
   {  int n = a.length-1;

      for (int gap = a.length/2 ; gap > 0 ; gap = gap/2) {
            for (int k = n/(gap+1)-1 ; k > 0 ; k-=gap)
               dyttNed(k,n,gap);
      }

      for (int k = n ; k > 0 ; k--)
         { dyttNed(0,k,1); bytt (0,k); }


    } // end shellTreeSort

}