//Preprocessor Directives

#include <iostream.h> //Included for Cin Cout
#include <conio.h>
#include <time.h>  //To get the elapsed CPU time used by a process, you can use the clock function which is within this library
#include <stdlib.h> //srand and rand functions are included in this directive
#include <fstream.h>


//Function Declarations
//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 = 100000;


ofstream outf("c:\\Output.txt",ios::app);//This prints the results to the c:drive


//Main
int main()
{
 


  long random_array[MAX_ARRAY_SIZE]; //Passes the 260000 to Random_Array.  MAX_ARRAY_SIZE is declared as a global
                                     //variable so any function can use it

  long array_sizes[] = {5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000,
  								45000, 50000, 55000, 60000, 65000, 70000, 75000, 80000,
                        85000, 90000, 95000, 100000};
									//Sizes of the array are declared here

  long num_elements;				//num_elements is declared here as long int

  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";

  //This function will use a for loop to call the different sort functions,
//with varing array sizes.
  for(long i = 0; i < 20; i++)
  {
    num_elements = array_sizes[i]; //array sizes[i] passes its values to num_elements




	getRandomIntegers(random_array, num_elements ); // random array has the value of MAX_ARRAY SIZE which is 260000
													//num elements now has the value of array_sizes

	start_time = clock(); //call the clock function at the beginning and end of the interval you want to time

	QuickSort(random_array, 0, num_elements ); //clock function starts before this function and ends after it

    end_time = clock();  //call the clock function at the beginning and end of the interval you want to time

    cout << "Quick   \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;
	//(double)CLOCKS_PER_SEC ---- This will allow you to see any milliseconds that pass since the sorting happens in less than a second.

    outf<< "Quick    \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)/(double)CLOCKS_PER_SEC << endl;

    //2)
	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;


	//3)
	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;


	//4)
	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 )
	{

  long i = Partition( array, left, right );

  QuickSort( array, left, i - 1);

  QuickSort( array, i + 1, right );

    }

}
/******************************************************************************/

//Function partitions the array
long Partition(long array[], long left, long right)
{
	long last, pivot, i;

	pivot = array[ left ];

	last = left;

	for (i = left + 1; i < right; i++)

		if (array[i] > pivot)
		{
			last++;
			Swap (array[last], array[i]);
		}

	Swap (array[left], array[last]);

	return last;
}


//MergeSort function
void MergeSort( long array[], long left, long right )
{

	if( left < right )
	 {

		long middle = ( left + right ) / 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 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;

  }

}