### Calculating sorting time for arrays

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?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134`` ``````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<
Last edited on
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.
I'm not sure what you mean when you say wrap it into a class and control it with a constructor/destructor.
it's like you've never used a chronometre
you need to start it at the beginning and stop it at the end.
 ``1234`` ``````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
Hello. I've actually haven't ever used this before. Would it also work if I just wrote it like this?

 ``12345678910111213141516`` ``````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
 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.
 ``123`` ``````clock_t const start = clock(); merge_sort( /* ... */ ); clock_t const finish = clock();``````
Last edited on
 ``123456789101112131415`` ``````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?
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.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758`` ``````#include #include #include #include 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.
Last edited on
 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.
 ``1234567891011121314151617181920`` ``````#include #include #include template struct Timer { std::chrono::time_point start{ std::chrono::system_clock::now() }; std::chrono::time_point stop; ~Timer() { stop = std::chrono::system_clock::now(); std::chrono::duration diff{ stop - start }; std::clog << diff.count() << std::endl; } }; int main() { Timer tmr; }``````
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.

Last edited on
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);`
Last edited on
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105`` ``````#include #include #include #include #include #include #include #include #include // 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)... ) ; // 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(wall_clock_end-wall_clock_start).count() / 1000.0 << " millisecs\n" ; } void std_sort( std::vector& seq ) { std::sort( seq.begin(), seq.end() ) ; } void heap_sort( std::vector& 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::iterator begin, std::vector::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& seq ) { merge( seq.begin(), seq.end() ) ; } void selection_sort( std::vector& 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& 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 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
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.
Last edited on
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.
Last edited on
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.

This is what I have currently:

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455`` ``````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<<","<

Do I have to put it somewhere into my main for each array?
Last edited on
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!).
Last edited on
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.

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253`` ``````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<<","<

When I change int to float it gives an error
 `cannot convert ‘float*’ to ‘int*’ for argument ‘1’ to ‘void insertionSort(int*, int)`
Last edited on
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.
Last edited on
Topic archived. No new replies allowed.