//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



int main()
{

  
  long random_array[MAX_ARRAY_SIZE];

  long array_sizes[] = {5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 55000, 60000,65000,70000,75000,80000,85000,90000,95000,100000}; 

  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++)  //Loop goes 20 times.. from 0-19
  {
    num_elements = array_sizes[i];  //First iteration array_sizes[i] which is the 0 location now goes into  num_elements

    getRandomIntegers(random_array, num_elements );  //First iteration...num_elements gets the value of array[i] which is the 0 location WHICH IS 5000. 
													//Random_array gets a number from within the MAX_ARRAY_SIZE  (long random_array[MAX_ARRAY_SIZE];)

    start_time = clock();                           //sTARTS the counter

    QuickSort(random_array, 0, num_elements );      //random which is max array size of 100000 , 5000 number of elements for the firt iteraton

    end_time = clock();								//ends counter

    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;

}

/******************************************************************************/

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

  }



}

/*******************************************************************************/

//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 ) //getRandomIntegers(random_array[max array size of 100000], long array_sizes[] = {5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 55000, 60000,65000,70000,75000,80000,85000,90000,95000,100000};  

													//Random_array gets a number from within the MAX_ARRAY_SIZE  (long random_array[MAX_ARRAY_SIZE];)

 {
  //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;

}

/******************************************************************************/
[b]//Quick Sort Function[/b]

void QuickSort( long array[], long left, long right)
 {

  if( right <= left )return; // if right (which is the largest number) is less than or equal to left

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

  QuickSort( array, left, i - 1);  // First subArray left/first to the pivot minus 1

  QuickSort( array, i + 1, right ); //Second subarray pivot+1 to the right/last

}

/******************************************************************************/
[b]//This function partitions the array[/b]


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 element after the pivot (++i) is less than the right

    while( y < array[--r] )  //while right element is less then the element before the right element
		
		if( r == 1 ) //if right location ==1

    break;              //stop

    if( i >= r )        //if left-1 location is greater than or equal to the right location

    break;              //break

    Swap( array[i], array[r] );   //swap  the right element with the left-1 element

  }

   Swap( array[i], array[right] );    //swap the right element with the left-1 element

   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 Insertion( long array[], long left, long right ) [b] //This function seems backwards but when I adjust it it does not run[/b]
 {


  long i;

  for( i = right; i > left; i-- )  //i is equal to the last number.  If i  is greater than the left number (5) then decrease the value of i (7)

    Swap( array[i - 1], array[i] );   //swap the location of array element[i]/right with the location of array element[i-1]

  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;

  }

}