#include <iostream.h>
#include <conio.h>
#include <time.h>
#include <limits.h>
#include <stdlib.h>
#include <fstream.h>
#include <math.h>
 
//Function-fills the array with random integers
void getRandomIntegers (long [], long);
 
//Function-will swap two long integer numbers
void Swap (long &, long &);
 
//Function-works with HeapSort to rearrange and adjust the heap
void Heapify (long [], long, long);
 
//Function-will be used with QuickSort to partition array
long Partition (long [], long, long);
 
//Function-sorts the array using the QuickSort method
void QuickSort (long [], long, long);
 
//Function-sorts the array using the MergeSort method
void MergeSort (long [], long, long);
 
//Function will be used with MergeSort to merge array back together.
void Merge (long [], long, long, long);
 
//Function-sorts the array using the HeapSort method
void HeapSort (long [], long, long);
 
//Function-sorts the array using the Insertion method
void Insertion (long [], long, long);
 
 
//Global variable constant
//This will be used by the various sorting functions
long const MAX_ARRAY_SIZE = 260000;
 
 
ofstream outf("c:\\Output.txt",ios::app);//This prints the results to the c:drive
 
 
int main()
{
 
//This function will use a for loop to call the different sort functions,
//with varing array sizes.
 
 
 
 
  long random_array[MAX_ARRAY_SIZE];
 
  long array_sizes[] = {100000, 110000, 130000, 150000, 170000, 190000, 200000, 210000, 230000, 250000, 255000, 260000}; 
 
  long num_elements;
 
  clock_t start_time, end_time;
 
  srand( time( NULL ));// This generates the random numbers
 
  cout << "Sort Type\t\t# of Elements\t\t\tTime(s)\n";
 
  cout << "--------\t\t-------------------\t\t-------\n";
 
  outf << "Sort Type\t\t# of Elements\t\t\tTime(s)\n";
 
  outf << "--------\t\t-------------------\t\t-------\n";
 
  for(long i = 0; i < 20; i++)
  {
    num_elements = array_sizes[i];
 
    getRandomIntegers(random_array, num_elements );
 
    start_time = clock();
 
    QuickSort(random_array, 0, num_elements );
 
    end_time = clock();
 
    cout << "Quick   \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
 
    outf<< "Quick    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
 
    getRandomIntegers( random_array, num_elements );
 
    start_time = clock();
 
    MergeSort( random_array, 0, num_elements );
 
    end_time = clock();
 
    cout << "Merge    \t\t\t" << num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
 
    outf << "Merge    \t\t\t" << num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
 
    getRandomIntegers( random_array, num_elements );
 
    start_time = clock();
 
    HeapSort( random_array, 0, num_elements );
 
    end_time = clock();
 
    cout << "Heap    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
 
    outf << "Heap    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
 
    getRandomIntegers( random_array, num_elements );
 
    start_time = clock();
 
    Insertion( random_array, 0, num_elements );
 
    end_time = clock();
 
    cout << "Insertion    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC<< endl << endl;
 
    outf << "Insertion    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl<<endl;
 
  }
  getch();
  return 0;
 
}
 
/******************************************************************************/
 
//This function is used by HeapSort to adjust the heap or "rearrange a heap to maintain the heap property"
void Heapify( long array[], long item, long num )
 {
 
  while( 2 * item <= num )
  {
    long j = 2 * item;
 
    if( j < num && array[j] < array[j + 1] ) j++;
 
    if( !( array[item], array[j]))
 
    break;
 
    Swap( array[item], array[j] ); item = j;
 
  }
 
}
 
/******************************************************************************/
 
void getRandomIntegers ( long arr[], long b )
 {
  //Fills an array(the first paramater) with
 
  //a specified amount( the second parameter ) of random integers.
 
  //The range of the random numbers will be from 0 to RAND_MAX.
 
 
 
  for( long i = 0; i < b; i++ )
 
    arr[i] = rand();
 
}
 
/******************************************************************************/
//Swap function, accepts two long integer values and swaps them.
 
void Swap( long &first, long &second )
 {
 
  long temp;
 
  temp = first;
 
  first = second;
 
  second = temp;
 
}
 
/******************************************************************************/
//Quick Sort Function
 
void QuickSort( long array[], long left, long right)
 {
 
  if( right <= left )return;
 
  long i = Partition( array, left, right );
 
  QuickSort( array, left, i - 1);
 
  QuickSort( array, i + 1, right );
 
}
 
/******************************************************************************/
//This function partitions the array
 
 
long Partition( long array[], long left, long right )
{
 
 
  long i = left - 1, r = right;
 
  long y = array[right];
 
  while( 1 )
  {
    while( array[++i] < y );
 
    while( y < array[--r] )if( r == 1 )
 
    break;
 
    if( i >= r )
 
    break;
 
    Swap( array[i], array[r] );
 
  }
 
   Swap( array[i], array[right] );
 
   return i;
 
}
 
/******************************************************************************/
//MergeSort function
 
void MergeSort( long array[], long left, long right )
{
 
 
  if( right <= left )
 
  return;
 
  long middle = ( right + left )/2;
 
  MergeSort( array, left, middle );
 
  MergeSort( array, middle + 1, right );
 
  Merge( array, left, middle, right );
 
}
 
/******************************************************************************/
//Merges arrays back together after they are split
 
void Merge( long array[], long left, long middle, long right )
{
 
 
  long i, j;
 
  long  static temp[MAX_ARRAY_SIZE];
 
  for( i = middle + 1; i > left; i-- )
 
    temp[i - 1] = array[i - 1];
 
  for( j = middle; j < right; j++ )
 
    temp[right + middle - j] = array[j + 1];
 
  for( long k = left; k <= right; k++ )
 
    if( temp[j] < temp[i] )
 
      array[k] = temp[j--];
 
    else
 
      array[k] = temp[i++];
 
}
 
/******************************************************************************/
 
 
void HeapSort( long array[], long left, long right )
{
 
  long k, num = right - left + 1;
 
  long *ip = array + left - 1;
 
  for( k = num/2; k >= 1; k-- )
 
  Heapify( ip, k, num );
 
  while ( num > 1 )
  {
 
    Swap( ip[1], ip[num] );
 
    Heapify( ip, 1, --num );
 
  }
 
 
 
}
 
/******************************************************************************/
 
void Insertion( long array[], long left, long right )
 {
 
 
  long i;
 
  for( i = right; i > left; i-- )
 
    Swap( array[i - 1], array[i] );
 
  for( i = left + 2; i <= right; i++ )
   {
 
    long j = i, item = array[i];
 
    while( item < array[j - 1] )
 
    {
 
    array[j] = array[j - 1];
    j--;
 
    }
 
    array[j] = item;
 
  }
 
}

long *random_array = new long[MAX_ARRAY_SIZE];

//This routine does the insertion sort
//This sorts array of object of template class T (T arr[]) & no. of elements in the array (int n)
template <class T>
void insertionSort(T arr[], int n)
{
	for (int i = 1; i < n; i++)
	{
		//start from 2nd node onwards
		T val = arr[i];
 
		for (int j = i - 1; j >= 0; j--)
		{
			if (arr[j] > val)
			{
				arr[j+1] = arr[j];
			}
			else
				break;
		}
		arr[j+1] = val;
	}
 
}