//
// Time comparison InsertionSort vs. ShellSort
//
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

//
// Shell Sort implementation using Shell's increments
//
void
ShellSort (int A[], int N)
{
  int i, j, Increment, Tmp;

  for (Increment = N/2; Increment > 0; Increment /= 2)
   {
    for (i = Increment; i < N; i++)
      {
        Tmp = A[i];
        for (j = i; j >= Increment; j -=  Increment)
          if (Tmp < A[j - Increment])
            A[j] = A[j - Increment];
          else
            break;
        A[j] = Tmp;
      }
    cout << Increment << ": ";
    for (int k = 0; k < N; k++)
      cout << A[k] << " ";
    cout << endl;
   }
}

//
// Insert Sort Implementation
//
void
InsertSort (int A[], int N)
{
  int j, P, Tmp;

  for (P = 1; P < N; P++)
    {
      Tmp = A[P];
      for (j = P; j > 0 && A[j-1] > Tmp; j--)
        A[j] = A[j-1];
      A[j] = Tmp;
    }
}

double
get_tm ()
{
  struct timeval tv;                                                            
  struct timezone tp;   

  gettimeofday (&tv, &tp);                                                      
  return (double)tv.tv_sec + (double)tv.tv_usec / 1000000.;
}

//
// Main Function
//
int 
main (int argn, char*argv[])
{
  int i, N;
  double itm = 0., stm = 0.;
  
  if (argn < 2)
    {
      cerr << " Size of the array is missing " << endl;
      return 0;
    }

  // Get the size
  N = atoi (argv[1]);
  int A[N], B[N], C[N];

  // Generate a random array
  srandom ( time(NULL));
  for (i = 0; i < N; i++)
    { A[i] = random () % (2*N); B[i] = A[i]; C[i] = A[i]; }

  // Get running time for Shell Sort
  stm -= get_tm ();
    ShellSort (A, N);
  stm += get_tm ();

  // Get running time for Insert Sort
  itm -= get_tm ();
    InsertSort (C, N);
  itm += get_tm ();

  // Print the array ( redirect stdout to /dev/null to avoid printing )
  cout << endl <<"Initial Array: ";
  for (i = 0; i < N; i++)                                                       
    cout << B[i] << " ";                                                        
  cout << endl;  
  cout << "ShellSorted Array: ";
  for (i = 0; i < N; i++)
    cout << A[i] << " ";
  cout << endl;
  cout << "InsertSorted Array: ";
  for (i = 0; i < N; i++)
    cout << C[i] << " ";
  cout << endl;

  // print running time on stderr
  cerr << endl << "InsertSort time: " << itm << endl;
  cerr << "ShellSort (Shell's) time: " << stm << endl;

  return 0;
}