Calculating sorting time for arrays

[CodingIsHard17]

Hello, I am trying to fix the current program to calculate how long it takes to sort each of the five arrays. Right now it is only calculating how long it takes to print the random numbers. Any help with how to change that?

selectionSort(selectionArray1, i);
myfile << endl << "\n- This is the list after being sorted by the selection sort method: ";
	for (i = 0; i < 1000; i++)	// loop for sorting rand numbs by selection sort
	{
    	myfile << selectionArray1[i] << " ";
	}


myfile << "\n" << endl;

{
	clock_t start = clock(); //place before calling a sorting function

	int selectionArray1[n];
		
	for(int i = 0; i < 1000; i++)
	{
		myfile << selectionArray1[i]<<"\t";
	}
	myfile<<endl;
 
	clock_t finish = clock();
	double doneTime = double(finish-start)/double(CLOCKS_PER_SEC/1000); 
	myfile << "- You took " << fixed << doneTime << setprecision(8) << " milliseconds\n";
	myfile << "\n -------------------------------------";
}


myfile << "\n\nRandom list of insertionArray: ";
	for (i = 0; i < 1000; i++)
	{
		myfile << insertionArray1[i] << " ";
	}
	
	insertionSort(insertionArray1, i);
	myfile << endl << "\n- This is the list after being sorted by the insertion sort method: ";

	for (i = 0; i < 1000; i++)	// loop for sorting rand numbs by insertion sort
	{
    	myfile << insertionArray1[i] << " ";
	}


myfile << "\n" << endl;

{
	clock_t start = clock(); 

	int insertionArray1[n];
		
	for(int i = 0; i < 1000; i++)
	{
		myfile << insertionArray1[i]<<"\t";
	}
	myfile << endl;
 
	clock_t finish = clock();
	double doneTime = double(finish-start)/double(CLOCKS_PER_SEC/1000); 
	myfile << "- You took " << fixed << doneTime << setprecision(8) << " milliseconds\n";
	myfile << "\n -------------------------------------";
}


myfile << "\n\nRandom list of quickArray: ";
	for (i = 0; i < 1000; i++)
	{
    	myfile << quickArray1[i] << " ";
	}

quickSort(quickArray1, 0, i-1);
myfile << endl << "\n- This is the list after being sorted by the quick sort method: ";
	for (i = 0; i < 1000; i++)
	{
    	myfile << quickArray1[i] << " ";
	}


myfile << "\n" << endl;

{
	clock_t start = clock(); 

	int quickArray1[n];
		
	for(int i = 0; i < 1000; i++)
	{
		myfile << quickArray1[i]<<"\t";
	}
	myfile << endl;
 
	clock_t finish = clock();
	double doneTime = double(finish-start)/double(CLOCKS_PER_SEC/1000); 
	myfile << "- You took " << fixed << doneTime << setprecision(8) << " milliseconds\n";
	myfile << "\n -------------------------------------";
}


myfile << "\n\nRandom list of mergeArray: ";
	for (i = 0; i < 1000; i++)
	{
    	myfile << mergeArray1[i] << " ";
	}

mergeSort(mergeArray1, 0, i-1);
myfile << endl << "\n- This is the list after being sorted by the merge sort method: ";
	
	
	for (i = 0; i < 1000; i++)	// loop for sorting rand numbs by merge sort
	{
    	myfile << mergeArray1[i] << " ";
	}


myfile << "\n" << endl;

{
	clock_t start = clock(); 

	int mergeArray1[n];
		
	for(int i = 0; i < 1000; i++)
	{
		myfile << mergeArray1[i]<<"\t";
	}
	myfile<<endl;
 
	clock_t finish = clock();
	double doneTime = double(finish-start)/double(CLOCKS_PER_SEC/1000); 
	myfile << "- You took " << fixed << doneTime << setprecision(8) << " milliseconds\n";
}

myfile.close();
return 0;
}

[kbw]

The standard library supports timing in a more rounded way. See: https://en.cppreference.com/w/cpp/chrono/system_clock/now

You can wrap the timer start/stop functionality in a class and use the constructor/destructor to control them. That'll cleanup your code significantly.

[CodingIsHard17]

I'm not sure what you mean when you say wrap it into a class and control it with a constructor/destructor.

[ne555]

it's like you've never used a chronometre
you need to start it at the beginning and stop it at the end.

clock_t start = clock(); 
mergeSort(array, 0, n);
clock_t finish = clock();
double doneTime = double(finish-start)/double(CLOCKS_PER_SEC/1000);

these programs may be helpful
https://linux.die.net/man/1/time
https://linux.die.net/man/1/ts


apart from that, ¿where are you filling your arrays? you seem to be printing uninitialised values

[CodingIsHard17]

Hello. I've actually haven't ever used this before. Would it also work if I just wrote it like this?

mergeSort(mergeArray1, 0, i-1);
myfile << endl << "\n- This is the list after being sorted by the merge sort method: ";
	
	clock_t start5 = clock(); 
	for (i = 0; i < 1000; i++)	// loop for sorting rand numbs by merge sort
	{
    	myfile << mergeArray1[i] << " ";
	}


myfile << "\n" << endl;

	clock_t finish5 = clock();
	double doneTime5 = double(finish5-start5)/double(CLOCKS_PER_SEC/1000); 
	myfile << "- You took " << fixed << doneTime5 << setprecision(8) << " milliseconds\n";

Or do I have to add it before mergeSort

[mbozzi]

Would it also work if I just wrote it like this?

No. C++ is eager - it does not wait to run code. The entire array is sorted immediately when you call merge_sort().

Because you're trying to measure the time required to perform the sort operation, and not the time required to print the resulting array, you need to "start" the clock immediately before sorting and "stop" the clock immediately after sorting.

clock_t const start = clock();
merge_sort( /* ... */ );
clock_t const finish = clock();

[CodingIsHard17]

clock_t start5 = clock();
    mergeSort(mergeArray, 0, i-1);
    clock_t finish5 = clock();
    myfile << endl << "- This is the list after being sorted by the merge sort method: ";
	
	for (i = 0; i < 10; i++)	// loop for sorting rand numbs by merge sort
	{
    	myfile << mergeArray[i] << " ";
	}


myfile << "\n" << endl;
 
	double doneTime5 = double(finish5-start5)/double(CLOCKS_PER_SEC/1000); 
	myfile << "- You took " << fixed << doneTime5 << setprecision(8) << " milliseconds\n";

It still reads only 0 seconds. Could it be something else?

[lastchance]

CodingIsHard wrote:

It still reads only 0 seconds. Could it be something else?

You aren't sorting enough numbers to take long enough to register between your clock ticks. cpp.sh has a better resolution clock than mine (and probably your) PC.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;


//======================================================================

void merge( int A[], int first, int mid, int last, int temp[] )
{
   int iA = first, iB = mid, n = last - first;
   for ( int t = 0; t < n; t++ ) temp[t] = ( iB == last ||  ( iA != mid && A[iA] < A[iB] ) ) ? A[iA++] : A[iB++];
   copy_n( temp, n, A + first );
}

void mergeSort( int A[], int n, int start, int temp[] )
{
   if ( n < 2 || ( n == 2 && A[start] <= A[start+1] ) ) return;
   int nlow = n / 2, nhigh = n - nlow, mid = start + nlow;
   mergeSort( A, nlow , start, temp );
   mergeSort( A, nhigh, mid  , temp );
   merge( A, start, mid, start + n, temp );
}

void mergeSort( int A[], int n )
{
   int *temp = new int[n];
   mergeSort( A, n, 0, temp );
   delete [] temp;
}

//======================================================================


int main()
{
   const int N = 1000000;    // Make N big enough to be worthwhile
   static int A[N];
   srand( time( 0 ) );
   for ( int &e : A ) e = 1 + rand() % 100;

   //cout << "Original: ";
   //for ( int e : A ) cout << e << ' ';

//////////////////
   clock_t t1 = clock();     // START YOUR CLOCK JUST ABOVE WHAT YOU WANT TO TIME
   
   mergeSort( A, N );        // Whatever you are timing
   
   clock_t t2 = clock();     // STOP YOUR CLOCK JUST BELOW WHAT YOU WANT TO TIME
//////////////////

   //cout << "\nSorted:   ";
   //for ( int e : A ) cout << e << ' ';

   cout << "\nSorting " << N << " numbers took " << 1000.0 * ( t2 - t1 ) / CLOCKS_PER_SEC << " milliseconds\n\n";
}

On cpp.sh with the default (-O2) optimisation (and best of 3 goes):

Sorting 1000000 numbers took 95.662 milliseconds

Sorting 100 numbers took 0.058 milliseconds

Sorting 10 numbers took 0.047 milliseconds

Sadly, std::sort is twice as fast, though.

[kbw]

I'm not sure what you mean when you say wrap it into a class and control it with a constructor/destructor.

If you think of a constructor/destructor pair as a means of running a pair of functions at the beginning and end of a block, you can see how a timer can be started/stopped using this technique.

If put together some minimal code that demonstrates my idea. I hope it helps.

#include <chrono>
#include <ratio>
#include <iostream>

template <typename T, typename RATIO>
struct Timer {
    std::chrono::time_point<std::chrono::system_clock> start{ std::chrono::system_clock::now() };
    std::chrono::time_point<std::chrono::system_clock> stop;

    ~Timer() {
        stop = std::chrono::system_clock::now();

        std::chrono::duration<T, RATIO> diff{ stop - start };
        std::clog << diff.count() << std::endl;
    }
};

int main() {
    Timer<double, std::milli> tmr;
}

[jonnin]

http://www.cplusplus.com/forum/beginner/263661/

Try to keep it in one place. @ 70 posts you should know this by now.

twice std::sort is pretty good. I get about the same for my shellsort on 6M items, which takes 2 sec (mine) on my slow laptop.
OP: lets say this stuff was linear, not faster as the array got smaller, using my numbers..
10 items would take 0.000003333333333 sec.
Its not linear, its much faster than this... you should expect a very, very small number.

[CodingIsHard17]

Sorry jonnin - wasn't getting no help.

Is that the right equation to get milliseconds?

1000.0 * ( t2 - t1 ) / CLOCKS_PER_SEC << " milliseconds\n\n";

double doneTime5 = double(finish5-start5)/double(CLOCKS_PER_SEC/1000);

OR if I just use seconds what is the difference of writing it like
double doneTime1 = double(finish1-start1)/(CLOCKS_PER_SEC);

or
double doneTime1 = float(finish1-start1)/(CLOCKS_PER_SEC);

[JLBorges]

#include <iostream>
#include <iomanip>
#include <string>
#include <ctime>
#include <chrono>
#include <type_traits>
#include <algorithm>
#include <cassert>
#include <random>


// print out processor and elapsed milliseconds to execute function fn
template < typename FN, typename... ARGS >
void time_it( const std::string& name, FN fn, ARGS&&... args )
{
    using namespace std::chrono ;
    // for measuring elapsed time:
    // use the high resolution clock if it is monotonic,
    // otherwise fall back to the steady clock
    using clock = typename std::conditional< high_resolution_clock::is_steady,
                                             high_resolution_clock, steady_clock >::type ;

    std::cout << '\n' << name << ":\n-------------\n" ;

    const auto wall_clock_start = clock::now() ;
    const auto processor_start = std::clock() ;

    fn( std::forward<ARGS>(args)... ) ; // call the function

    const auto processor_end = std::clock() ;
    const auto wall_clock_end = clock::now() ;

    // compute and print result
    std::cout << std::fixed << std::setprecision(3) 
              << "processor: "
              << (processor_end-processor_start) * 1000.0 / CLOCKS_PER_SEC << " millisecs\n"
              << "  elapsed: "
              << duration_cast<microseconds>(wall_clock_end-wall_clock_start).count() / 1000.0 << " millisecs\n" ;
}

void std_sort( std::vector<std::size_t>& seq ) { std::sort( seq.begin(), seq.end() ) ; }

void heap_sort( std::vector<std::size_t>& seq )
{
    // https://en.cppreference.com/w/cpp/algorithm/make_heap
    std::make_heap( seq.begin(), seq.end() ) ;

    // https://en.cppreference.com/w/cpp/algorithm/sort_heap
    std::sort_heap( seq.begin(), seq.end() ) ;
}

void merge( std::vector<std::size_t>::iterator begin, std::vector<std::size_t>::iterator end )
{
    // https://en.cppreference.com/w/cpp/iterator/distance
    const auto dist = std::distance( begin, end ) ;

    if( dist > 1 )
    {
        // https://en.cppreference.com/w/cpp/iterator/next
        const auto mid = std::next( begin, dist/2 ) ;
        merge( begin, mid ) ;
        merge( mid, end ) ;

        // https://en.cppreference.com/w/cpp/algorithm/inplace_merge
        std::inplace_merge( begin, mid, end ) ;
    }
}

void merge_sort( std::vector<std::size_t>& seq ) { merge( seq.begin(), seq.end() ) ; }

void selection_sort( std::vector<std::size_t>& seq )
{
    const auto end = seq.end() ;
    for( auto iter = seq.begin() ; iter != end ; ++iter )
    {
        // https://en.cppreference.com/w/cpp/algorithm/min_element
        // https://en.cppreference.com/w/cpp/algorithm/iter_swap
        std::iter_swap( iter, std::min_element( iter, end ) ) ;
    }
}

// helper function to time the sort of our vector
template < typename SORT_FN >
void sort_and_time( const std::string& name, SORT_FN sort_fn, const std::vector<std::size_t>& test_data )
{
    auto vec = test_data ; // make a copy of the test data
    time_it( name, sort_fn, vec ) ; // time the sort of the copy
    assert( std::is_sorted( vec.begin(), vec.end() ) ) ; // sanity check
}

int main()
{
   const std::size_t N = 32'000 ;

   // create a vector of size N, fill it with random numbers
   std::vector<std::size_t> test_data(N) ;
   std::mt19937 rng( std::random_device{}() ) ;
   std::generate( test_data.begin(), test_data.end(), rng ) ;

   // print out timings of the three sorts
   sort_and_time( "std sort", std_sort, test_data ) ;
   sort_and_time( "heap sort", heap_sort, test_data ) ;
   sort_and_time( "merge sort", merge_sort, test_data ) ;
   sort_and_time( "selection sort", selection_sort, test_data ) ;
} 

http://coliru.stacked-crooked.com/a/48342169eaabb331

[jonnin]

Is that the right equation to get milliseconds?

work through it, think it out...
clocks/clocks/sec = seconds. 1 sec is 1000 ms, so *1000 is correct to convert sec to ms.


but clock is unable to register these small values. clock is for things that take seconds to execute... it will give you zero all day long for 10 items unless you are running this code on a wristwatch from the 1980s. Either sort a few million items to get a value from clock, or use a better timer (shown about 10 times now... use the darn high res timers we are showing you. its nearly the same code as clock, and its a ton better .... don't be stubborn about this lol).
JL even converted it so high res replaced clock so you don't have to fix anything. That was slick.

[CodingIsHard17]

Hello,

I kept it just at seconds and it turned out like I wanted it to. Can someone point me in the direction of now deleting those arrays and to increase the array size and output new numbers?

So: using the new operator to create the arrays and then have them destroyed using the delete operator once they've been written to a file.

[jonnin]

its pretty easy to do that.

int *a = new int[100];
...blah blah. fill it in, sort it, whatever.
… oh noes, it needed to be bigger:
int* b = new int[1000];
for(int j = 0; j < 100; j++)
b[j] = a[j]; //memcpy would be better here for simple types, loop for objects that can't be byte copied
delete [] a; //the 100 array is gone. the data is safely copied to b's data area.
a = b; //optional: move b back to a, just the pointer. if you need to.
b = 0; //optional. just being careful with having 2 things point to same memory can be confusing. b was sort of a temporary, so I nulled it out.

[CodingIsHard17]

This is what I have currently:

int main()
{
	ofstream myfile;
  	myfile.open ("Results.csv");
  	
  	double time0 = 0.000001;
    double time1 = 0.23;
    double time2 = 0.0001;
    double time3 = 0.567;
    double time4 = 0.654;
    double time5 = 0.231;
    
    myfile << "Array Size,Bubble Sort Time,Selection Sort Time, Insertion Sort Time, Quick Sort Time, Merge Sort Time\n";
    myfile << "100,0.002,0.0001,\n";
    myfile << 200<<","<<time0<<","<<time1<<","<<time2<<","<<time3<<","<<time4<<","<<time5<<","<<"\n";
  	
  	int i, j, n=1000, temp;
  	int bubbleArray [n]; // sets each array equal to the size of n
  	int selectionArray [n];
  	int insertionArray [n];
  	int quickArray [n];
  	int mergeArray [n];
  	
  	srand (time(NULL));
  	
  	myfile << "Random list of bubbleArray: ";
  	
  	for (i = 0; i < 1000; i++) // loop generating 1000 random numbers out of 2000000
{
    int value = rand() % 2000000; // Random from 1 through 2000000 ; allows for all arrays to generate the same random numbers
    bubbleArray [i] = value; // this and the other arrays are set equal to value to allow for the same numbers to be selected out of 2000000
    selectionArray [i] = value;
    insertionArray [i] = value;
    quickArray [i] = value;
    mergeArray [i] = value;
        
    myfile << bubbleArray[i] << " "; // tells the program to print the random values for the bubble array to indicated file.

}

    clock_t start1 = clock(); // the clock starts once the program is called to sort.
    bubbleSort(bubbleArray, i);
    clock_t finish1 = clock(); //stops the clock once the array finishes being sorted.
    myfile << endl << "\n- This is the list after being sorted by the bubble sort method: ";
 
	for (i = 0; i < 1000; i++) 	// loop sorting random numbers by bubble sort.
	{
	myfile << bubbleArray[i] << " "; // tells the program to print the sorted values for the bubble array to indicated file.
    }
	
	myfile << "\n" << endl;
		
	double doneTime1 = float(finish1-start1)/(CLOCKS_PER_SEC); 
	myfile << "- You took " << fixed << doneTime1 << setprecision(12) << " seconds\n"; // sets the seconds to 12 decimal places.
	myfile << "\n -------------------------------------";

Do I have to put it somewhere into my main for each array?

[jonnin]

1)
int mergeArray [n]; is not legal in c++. its a compiler extension to the language. Its bad practice.
2)
you didnt use any pointers, so I have no idea what you are asking. you may NOT change the size of arrays, and you may NOT have variable sized arrays (which you do, N is a variable). You must use vectors or pointers or something like that which can legally be resized if you want to resize.
3) I still see clock(). why?

Im happy to help you, but I can't make sense of where you are and where you want to go right now. If you want to resize, you need to change the code to support that, with pointers (and I gave an example of those) or vectors (better!).

[CodingIsHard17]

I was told that I couldn't use anything other than clock() and that's why it is still there.

I tried adding pointers, but now instead of the lists other than bubbleArray being random they are all printing in a sorted format.

int main()
{
	ofstream myfile;
  	myfile.open ("GroupAssignment2Results.csv");
  	
  	double time0 = 0.000001;
    double time1 = 0.23;
    double time2 = 0.0001;
    double time3 = 0.567;
    double time4 = 0.654;
    double time5 = 0;
    
  
    myfile << "Array Size,Bubble Sort Time,Selection Sort Time, Insertion Sort Time, Quick Sort Time, Merge Sort Time\n";
    myfile << "100,0.002,0.0001,\n";
    myfile << 200<<","<<time0<<","<<time1<<","<<time2<<","<<time3<<","<<time4<<","<<time5<<","<<"\n";
  	
  	int i, j, temp;
  	int n[1000];
  	int *bubbleArray; // a pointer
  	int *selectionArray;
  	int *insertionArray;
  	int *quickArray;
  	int *mergeArray;
  	
  	bubbleArray = n; // by setting each array equal to n they are all set to be 1000 values
  	selectionArray = n;
  	insertionArray = n;
  	quickArray = n;
  	mergeArray = n;
  
  	srand (time(NULL));
  	
  	myfile << "Random list of bubbleArray: ";
  	
  	for (i = 0; i < 1000; i++) // loop generating 1000 random numbers out of 2000000
{
    int value = rand() % 2000000; // Random from 1 through 2000000 ; allows for all arrays to generate the same random numbers
    bubbleArray [i] = value; // this and the other arrays are set equal to value to allow for the same numbers to be selected out of 2000000
    selectionArray [i] = value;
    insertionArray [i] = value;
    quickArray [i] = value;
    mergeArray [i] = value;
        
    myfile << bubbleArray[i] << " "; // tells the program to print the random values for the bubble array to indicated file.

}

    clock_t start1 = clock(); // the clock starts once the program is called to sort.
    bubbleSort(bubbleArray, i);
    clock_t finish1 = clock(); //stops the clock once the array finishes being sorted.
    myfile << endl << "\n- This is the list after being sorted by the bubble sort method: ";
 

When I change int to float it gives an error

cannot convert ‘float*’ to ‘int*’ for argument ‘1’ to ‘void insertionSort(int*, int)

[jonnin]

pointers are strongly typed. you cannot send a float* to an int*
the reason is memory. an int could be 16 bytes and a float 32 on some system, and the type tells the cpu how many bytes of ram each array location consumes. you occasionally turn pointers to byte pointers with explicit casting for various reasons, but that is advanced and we can talk about it later, and for similar bit or byte magic you may do other odd things with casting pointers, but table that idea for now. You are not ready for a few more weeks. Get your head around the normal uses first :)

there are ways to make your sort work no matter what you pass in, as long as the type passed in has a comparison operator. This is template programming, which is also a bit advanced; have you started to look at classes and OOP yet?

you are making ALL YOUR POINTERS point to THE SAME EXACT MEMORY so bubble sort SORTS ALL YOUR ARRAYS because they ARE ALL THE SAME ARRAY.

bubbleArray = n; // by setting each array equal to n they are all set to be 1000 values
selectionArray = n;
insertionArray = n;
quickArray = n;
mergeArray = n;

^^^^^^^^^ All those pointers are pointing to the exact same memory block, that is, they are all effectively a rename for 'n' array. You may as well be saying 'n' when you use ANY of them.

you can make more arrays and point to them, but why bother with the pointer if you do that? Its just a reference really, if you do that.
do you want dynamic memory and a resize or not? I gave you the code.
int* n = new int[1000];
fill it in
sort it
resize it:
int * tmp = new int[2000];
for()... copy n to tmp
delete[] n; //release old memory
n = tmp; //switcheroo. n is now size 2000 and the first 1000 are the old n, the rest are 'empty' (uninitialized, though maybe new sets to zero, I lose track of some features)

A pointer to something THAT YOU ALREADY HAVE A NAMED VARIABLE FOR** is NOT DYNAMIC MEMORY. Its just a pseudo-reference / alias. These have uses, but its NOT DYNAMIC MEMORY.


**Not counting if the named variable is itself dynamic memory.