# Sorting Algorithms with Time

• 05-02-2005
silicon
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

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```
• 05-02-2005
silicon
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

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;   } }```
• 05-03-2005
Salem
How to time code accurately has been discussed before - try a board search.

FYI, to be a truly comparable test, you should generate a random set of data just once for each loop, and pass copies of that data to each sort function.
• 05-03-2005
joshdick
Quote:

Originally Posted by silicon
//Main function.

Now I've seen everything :rolleyes: