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

#include "sorting.h"


//
//
//
void
print_vector (int A[], int N)
{
  for (int i = 0; i < N; i++) 
    cout << A[i] << " ";
  cout << endl;
}

//
//
//
void
Swap (int& a, int& b)
{
  int t = a;
  a = b;
  b = t;
}

//
// Get a time stamp
//
double
get_time ()
{
  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 tm = 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];

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

  // Get running time for Selection Sort
  for (i = 0; i < N; i++) { A[i] = B[i]; }
  tm -= get_time (); SelectionSort (A, N); tm += get_time ();

  print_vector (A, N);
  cerr << "SelectionSort: " << tm << endl;

  // Get running time for Bubble Sort
  for (i = 0; i < N; i++) { A[i] = B[i]; }
  tm = -get_time (); BubbleSort (A, N); tm += get_time ();

  print_vector (A, N);
  cerr << "BubbleSort: " << tm << endl;

  // Get running time for Insert Sort
  for (i = 0; i < N; i++) { A[i] = B[i]; }
  tm = -get_time (); InsertSort (A, N); tm += get_time ();

  print_vector (A, N);
  cerr << "InsertSort: " << tm << endl;

  // Get running time for Shell Sort
  for (i = 0; i < N; i++) { A[i] = B[i]; }
  tm = -get_time (); ShellSort (A, N); tm += get_time ();

  print_vector (A, N);
  cerr << "ShellSort: " << tm << endl;

  // Get running time for Shell Sort H
  for (i = 0; i < N; i++) { A[i] = B[i]; }
  tm = -get_time (); ShellSortH (A, N); tm += get_time ();

  print_vector (A, N);
  cerr << "ShellSortH: " << tm << endl;

  // Get running time for Merge Sort
  for (i = 0; i < N; i++) { A[i] = B[i]; }
  tm = -get_time (); MergeSort (A, N); tm += get_time ();

  print_vector (A, N);
  cerr << "MergeSort: " << tm << endl;

  // Get running time for Quick Sort
  for (i = 0; i < N; i++) { A[i] = B[i]; }
  tm = -get_time (); QuickSortR (A, N); tm += get_time ();

  print_vector (A, N);
  cerr << "QuickSortR: " << tm << endl;

  // Get running time for Quick Sort
  for (i = 0; i < N; i++) { A[i] = B[i]; }
  tm = -get_time (); QuickSortI (A, N); tm += get_time ();

  print_vector (A, N);
  cerr << "QuickSortI: " << tm << endl;

  print_vector (B, N);

  return 0;
}