Sorting Algorithms by Time

silicon · #1 02-May-2005, 20:16

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

CPP / C++ / C 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:

Code:

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

Stack Overflow · #2 02-May-2005, 20:51

Hello,

I've ran into this problem before. I know of a way to fix this. There are two steps.

Step #1
Change all the occurrences of:

CPP / C++ / C Code:

(end_time - start_time)

To:

CPP / C++ / C Code:

(end_time - start_time)/(double)CLOCKS_PER_SEC

Since you want to see more than just the seconds that pass. This will allow you to see any milliseconds that pass.

Step 2
Change all of the occurrences of:

CPP / C++ / C Code:

*_time = time( NULL );

To:

CPP / C++ / C Code:

*_time = clock();

Where * denotes start and end. So both of the variables will equal clock() rather than time( NULL )

- Stack Overflow

WaltP · #3 02-May-2005, 21:19

Here's what I see in your code:

CPP / C++ / C Code:

#include <iostream.h>
#include <conio.h>
#include <time.h>
#include <limits.h>
#include <stdlib.h>
#include <fstream.h>
#include <math.h>

You should be using the newer .h-less headers. Also, for what you're doing, conio.h is not necessary. Change getch() to cin.get().

CPP / C++ / C Code:

//The constant is used by various sort functions
//This will be a global variable constant
long const MAX_ARRAY_SIZE = 200000;
...
  long random_array[MAX_ARRAY_SIZE];

  long array_sizes[] = {10000, 30000, 50000, 70000, 90000, 100000, 200000};
...
  for(long i = 0; i < 20; i++)
  {
    num_elements = array_sizes[i];

How many elements does array_sizes[6] hold? You are blowing past your array.

CPP / C++ / C Code:

    getRandomNumbers(random_array, num_elements );// fills array with random numbers
...
    start_time = time( NULL );
    QuickSort(random_array, 0, num_elements );
    end_time = time( NULL );
...
    getRandomNumbers( random_array, num_elements );
    start_time = time( NULL );
    MergeSort( random_array, 0, num_elements );
    end_time = time( NULL );

To compare times correctly, you should be using the same array sorted with each sort type. Add a function called loadRandomArray() that will copy the array values created in getRandomNumbers() into your sort array so you can sort the same values for each trial. Yes, this will require a second array...

CPP / C++ / C Code:

//output:

Sort Type               # of Elements                   Time(s)
--------                -------------------             -------
Quick                           10000                   0
Merge                           10000                   0
Heap                            10000                   0
Insertion                       4                       1115086283

Your INSERTION sort seems to be blowing thru your sort array, taking other values with it. num_elements is no longer 10000, and your size array has been trashed. I'll bet the sort is using more than your alotted 200000 bytes somehow.

Also, the time() function only has a resolution of 1 second. Many, if not most, of your sorts will probably run in under a second. For this type of project you'll want a millisecond resolution, which means looking into other time functions. Look thru your book or google for other options you can use.

Dave Sinkula · #4 02-May-2005, 21:42

[Also, cross-posted.]

silicon · #5 02-May-2005, 21:54

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

I will now work on what you suggested WaltP

Thanks for all of you help

I really appreaciate it

CPP / C++ / C 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;

  }

}

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Simulation Problem	wu_weidong	C++ Forum	7	12-Mar-2005 22:56
[CONTEST?]Data Structure Test	dsmith	C Programming Language	2	06-Jun-2004 15:13
Re: Programming Techniques	WaltP	C Programming Language	0	09-Mar-2004 23:56
time Problem	zuzupus	MySQL / PHP Forum	9	24-Jul-2003 07:02

Sorting Algorithms by Time

Adjustments Made to Sorting Algorithms-Time