Sorting Algorithms with Time
Hello again everyone. We have completed a project after a few months and a lot of help but for some reason we are still having problems. The project compiles properly without errors but the results are incorrect. Basically we are using 4 sorting algorithms in order to calculate how much time it takes to generate random numbers and the time that is taken. We have no problems generating the integers but the times seem to be way off (Time seems to always be 0) . My brain is fried and so are my teammates'. I was hoping that someone could point us in the right direction as to why the times are off. We are very new to the time function and had to read a few books and templates to complete this much
I've included our output at the end of the code. Please let us know if we are overlooking something simple
Thanks in advance
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
Adjustments to Sorting Algorithms-Time
Hello, I've rewritten the code and now see times that look correct. I know understand that the 0's were because the sorting happened under 1 second.
It still doesn't give me the times for everything but it seems that I am now on the right track
Thanks for your help
Is there a way that I can a more precise time so that I can get a time for every method
Code:
#include <iostream.h>
#include <conio.h>
#include <time.h>
#include <limits.h>
#include <stdlib.h>
#include <fstream.h>
#include <math.h>
//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 bac 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 = 2000;
ofstream outf("c:\\Output.txt",ios::app);//This prints the results to the c:drive
//Main
int main()
{
//This function will use a for loop to call the different sort functions,
//with varing array sizes.
cout << "\nSorting in progress: Please wait\n"
<< "\n ***************************************************\n";
long random_array[MAX_ARRAY_SIZE];
long array_sizes[] = {100, 500, 1000, 2500, 5000, 10000, 20000};
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++)
{
num_elements = array_sizes[i];
getRandomIntegers(random_array, num_elements );
start_time = clock();
QuickSort(random_array, 0, num_elements );
end_time = clock();
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;
}
/******************************************************************************/
//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 )return;
long i = Partition( array, left, right );
QuickSort( array, left, i - 1);
QuickSort( array, i + 1, right );
}
/******************************************************************************/
//This function partitions the array
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( y < array[--r] )if( r == 1 )
break;
if( i >= r )
break;
Swap( array[i], array[r] );
}
Swap( array[i], array[right] );
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 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;
}
}
