Thread: Merge and Heap..which is really faster

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    Merge and Heap..which is really faster

    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
    Code:
      
    
    
    
    
    //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
    
    */

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    To be honest, I've heard that heap is usually faster. They both have the same best, worst, and average running time, but considering Merge is constantly creating new arrays it tends to run a little slower.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I believe, however, that you have more optimization options with merge sort. Straight merge sort, natural merge sort. Perhaps you can find a linear in-place merge so you get rid of the allocation.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 10:33 AM