Hello everyone, my code is finally complete thanks to all of your help. One questions I have is regarding the reslts. I thought that Merge was faster than a heap sort. In my results however (when run on Borland c++) Heap comes out with a faster sorting time. The functions seem to be correct. Please help.....

Thanks

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

  }

}


//Output:

/*
Programmers: David Arocha, Geneva Bell, and Steve Toussaint.

This program compares and records the time taken to sort an array of random
integers using Merge, Quick, Heap, and Insertion sort algorithms.

Sorting in progress: Please wait

 ***************************************************
Sort Type               # of Elements                   Time(s)
--------                -------------------             -------
Quick                           5000                    0
Merge                           5000                    0.11
Heap                            5000                    0
Insertion                       5000                    0.015

Quick                           10000                   0
Merge                           10000                   0.235
Heap                            10000                   0.015
Insertion                       10000                   0.047

Quick                           15000                   0
Merge                           15000                   0.297
Heap                            15000                   0
Insertion                       15000                   0.109

Quick                           20000                   0
Merge                           20000                   0.406
Heap                            20000                   0
Insertion                       20000                   0.203

Quick                           25000                   0.016
Merge                           25000                   0.484
Heap                            25000                   0.016
Insertion                       25000                   0.312

Quick                           30000                   0
Merge                           30000                   0.594
Heap                            30000                   0
Insertion                       30000                   0.453

Quick                           35000                   0
Merge                           35000                   0.703
Heap                            35000                   0.016
Insertion                       35000                   0.64

Quick                           40000                   0.016
Merge                           40000                   0.797
Heap                            40000                   0.015
Insertion                       40000                   0.907

Quick                           45000                   0
Merge                           45000                   1.172
Heap                            45000                   0.031
Insertion                       45000                   1.125

Quick                           50000                   0.047
Merge                           50000                   1.109
Heap                            50000                   0.016
Insertion                       50000                   1.516

Quick                           55000                   0.015
Merge                           55000                   1.328
Heap                            55000                   0.032
Insertion                       55000                   1.921

Quick                           60000                   0.032
Merge                           60000                   1.281
Heap                            60000                   0.015
Insertion                       60000                   2.141

Quick                           65000                   0.015
Merge                           65000                   1.61
Heap                            65000                   0.031
Insertion                       65000                   2.375

Quick                           70000                   0.015
Merge                           70000                   1.375
Heap                            70000                   0.032
Insertion                       70000                   2.546

Quick                           75000                   0.016
Merge                           75000                   1.468
Heap                            75000                   0.032
Insertion                       75000                   3.062

Quick                           80000                   0.015
Merge                           80000                   1.579
Heap                            80000                   0.031
Insertion                       80000                   3.734

Quick                           85000                   0.031
Merge                           85000                   1.688
Heap                            85000                   0.031
Insertion                       85000                   4.687

Quick                           90000                   0.032
Merge                           90000                   1.75
Heap                            90000                   0.031
Insertion                       90000                   5.719

Quick                           95000                   0.016
Merge                           95000                   1.844
Heap                            95000                   0.047
Insertion                       95000                   7.047

Quick                           100000                  0.031
Merge                           100000                  1.953
Heap                            100000                  0.047
Insertion                       100000                  8.516

*/

Congratulations, you've just discovered the difference between theoretical upper bounds and real world implementations. In theory, merge sort is slightly faster than heap sort. In practice, the merge sort algorithm could be implemented poorly (or naively) and heap sort will blow it away.

This article has been dead for over six months. Start a new discussion instead.