Hello everyone, I just wanted to thank you in advance for all of your help.
My code is now working properly except for one thing. The insertion part feels like it takes about 5 minutes to complete. I know that this method is the slowest of the 4
I was wondering if there a problem with the way it was written
My partner wrote this insertion sort function and it does work...but runs very slowly and I am having problems adjusting
it since this code will not work on Visual C++...it will however work on Borland c++
#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 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 = 260000;
ofstream outf("c:\\Output.txt",ios::app);//This prints the results to the c:drive
int main()
{
//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[] = {100000, 110000, 130000, 150000, 170000, 190000, 200000, 210000, 230000, 250000, 255000, 260000};
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;
}
}
