Sorting Algorithms with Time

This is a discussion on Sorting Algorithms with Time within the C++ Programming forums, part of the General Programming Boards category; Hello again everyone. We have completed a project after a few months and a lot of help but for some ...

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    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

  2. #2
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    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;
    
      }
    
    }

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Quote Originally Posted by silicon
    //Main function.
    Now I've seen everything
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sentinel in sorting algorithms
    By Albinoswordfish in forum C Programming
    Replies: 2
    Last Post: 12-17-2008, 02:21 AM
  2. Using pointers
    By Big_0_72 in forum C Programming
    Replies: 3
    Last Post: 10-28-2008, 07:51 PM
  3. need help in time zone
    By Gong in forum C++ Programming
    Replies: 2
    Last Post: 01-03-2007, 03:44 AM
  4. Help with assignment!
    By RVDFan85 in forum C++ Programming
    Replies: 12
    Last Post: 12-02-2006, 11:46 PM
  5. Sending an email in C program
    By Moony in forum C Programming
    Replies: 28
    Last Post: 10-19-2006, 10:42 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21