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