Code:
//Write a program that compares and records the time taken to sort an array of integers
//The program must generate random integers.
#include <iostream.h>
#include <conio.h>
#include <time.h>
#include <limits.h>
#include <stdlib.h>
#include <fstream.h>
#include <math.h>
//function will fill an array with random numbers
void getRandomNumbers (long [], long);
//function will swap two long integer numbers
void Swap(long &, long &);
//function works with HeapSort to adjust heap
void Heapify(long[], long, long);
//function will be used with QuickSort to partition array
long Partition(long[], long, long);
//function will sort an array using the QuickSort method
void QuickSort(long[], long, long);
//function will sort an array using the MergeSort method
void MergeSort(long[], long, long);
//function will work with MergeSort.
void Merge(long[], long, long, long);
//function will sort an array using the HeapSort method
void HeapSort(long[], long, long);
//function will sort an array using Insertion method
void Insertion(long[], long, long);
//The constant is used by various sort functions
//This will be a global variable constant
long const MAX_ARRAY_SIZE = 200000;
ofstream outf("c:\\Output.txt",ios::app);//Prints output to the c:drive
int main()
{
//Main function.
//This function will use a for loop to call the different sort functions,
//with varing array sizes.
long random_array[MAX_ARRAY_SIZE];
long array_sizes[] = {10000, 30000, 50000, 70000, 90000, 100000, 200000};
long num_elements;
time_t start_time, end_time;
srand( time( NULL ));// starts random nubmer gererator.
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++)
{
num_elements = array_sizes[i];
getRandomNumbers(random_array, num_elements );// fills array with random numbers
start_time = time( NULL );
QuickSort(random_array, 0, num_elements );
end_time = time( NULL );
cout << "Quick \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time) << endl;
outf<< "Quick \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time) << endl;
getRandomNumbers( random_array, num_elements );
start_time = time( NULL );
MergeSort( random_array, 0, num_elements );
end_time = time( NULL );
cout << "Merge \t\t\t" << num_elements << "\t\t\t" << (end_time - start_time) << endl;
outf << "Merge \t\t\t" << num_elements << "\t\t\t" << (end_time - start_time) << endl;
getRandomNumbers( random_array, num_elements );
start_time = time( NULL );
HeapSort( random_array, 0, num_elements );
end_time = time( NULL );
cout << "Heap \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time) << endl;
outf << "Heap \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time) << endl;
getRandomNumbers( random_array, num_elements );
start_time = time( NULL );
Insertion( random_array, 0, num_elements );
end_time = time( NULL );
cout << "Insertion \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time)<< endl << endl;
outf << "Insertion \t\t\t"<< num_elements << "\t\t\t" << (end_time - start_time) << endl<<endl;
}
getch();
return 0;
}
/******************************************************************************/
void Heapify( long array[], long item, long num )
{
//This function is used by HeapSort to maintain the array
//as a ordered heap.
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 getRandomNumbers ( long arr[], long b )
{
//getRandomNumbers function will fill 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();
}
/******************************************************************************/
void Swap( long &first, long &second )
{
//Swap function, accepts two long integers values by reference,and swaps them.
//Many sort functions involve the swapping of two numbers.
long temp;
temp = first;
first = second;
second = temp;
}
/******************************************************************************/
void QuickSort( long array[], long left, long right)
{
//This is the quick sort function.
if( right <= left )return;
long i = Partition( array, left, right );
QuickSort( array, left, i - 1);
QuickSort( array, i + 1, right );
}
/******************************************************************************/
long Partition( long array[], long left, long right )
{
//This function is used by QuickSort function andpartitions the array so it
//can be sorted recursively.
long i = left - 1, r = right;
long y = array[right];
while( 1 )
{
while( array[++i] < y );
while( y < array[--r] )if( r == 1 )
break;
if( i >= r )
break;
Swap( array[i], array[r] );
}
Swap( array[i], array[right] );
return i;
}
/******************************************************************************/
void MergeSort( long array[], long left, long right ) //The MergeSort function
{
if( right <= left )
return;
long middle = ( right + left )/2;
MergeSort( array, left, middle );
MergeSort( array, middle + 1, right );
Merge( array, left, middle, right );
}
/******************************************************************************/
void Merge( long array[], long left, long middle, long right )
{
//A MergeSort helper function
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 HeapSort( long array[], long left, long right )
{
//This is the HeapSort function.
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 )
{
//main function for Insertion sort.
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:
Sort Type # of Elements Time(s)
-------- ------------------- -------
Quick 10000 0
Merge 10000 0
Heap 10000 0
Insertion 4 1115086283
Quick 9 0
Merge 9 0
Heap 9 0
Insertion 9 0
Quick 11 0
Merge 11 0
Heap 11 0
Insertion 11 0
Quick 11 0
Merge 11 0
Heap 11 0
Insertion 11 0
Quick 18 0
Merge 18 0
Heap 18 0
Insertion 18 0
Quick 21 0
Merge 21 0
Heap 21 0
Insertion 21 0
Quick 26 0
Merge 26 0
Heap 26 0
Insertion 26 0
Quick 336 0
Merge 336 0
Heap 336 0
Insertion 336 0
Quick 227 0
Merge 227 0
Heap 227 0
Insertion 227 0
Quick 543 0
Merge 543 0
Heap 543 0
Insertion 543 0
Quick 133 0
Merge 133 0
Heap 133 0
Insertion 133 0
Quick 820 0
Merge 820 0
Heap 820 0
Insertion 820 0
Quick 395 0
Merge 395 0
Heap 395 0
Insertion 395 0
Quick 480 0
Merge 480 0
Heap 480 0
Insertion 480 0
Quick 536 0
Merge 536 0
Heap 536 0
Insertion 1115086286 0
Quick 11 0
Merge 11 0
Heap 11 0
Insertion 11 0
Quick 17 0
Merge 17 0
Heap 17 0
Insertion 17 0
Quick 18 0
Merge 18 0
Heap 18 0
Insertion 18 0
Quick 383 0
Merge 383 0
Heap 383 0
Insertion 383 0
Quick 159 0
Merge 159 0
Heap 159 0
Insertion 159 0
Quick 313 0
Merge 313 0
Heap 313 0
Insertion 313 0
Quick 833 0
Merge 833 0
Heap 833 0
Insertion 833 0
Quick 135 0
Merge 135 0
Heap 135 0
Insertion 135 0
Quick 1513 0
Merge 1513 0
Heap 1513 0
Insertion 1513 0
Quick 77 0
Merge 77 0
Heap 77 0
Insertion 77 0
Quick 6430 0
Merge 6430 0
Heap 6430 0
Insertion 14 1115086282
Quick 536 0
Merge 536 0
Heap 536 0
Insertion 536 0
Quick 7 0
Merge 7 0
Heap 7 0
Insertion 7 0
Quick 8 0
Merge 8 0
Heap 8 0
Insertion 8 0
Quick 9 0
Merge 9 0
Heap 9 0
Insertion 9 0
Quick 5256 0
Merge 5256 0
Heap 5256 0
Insertion 1115086286 0
Quick 6430 0
Merge 6430 0
Heap 6430 0
Insertion 6430 0
Quick 536 0
Merge 536 0
Heap 536 0
Insertion 1115086286 0
Press any key to continue