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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
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;
}
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.
1
2
3
4
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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.
1
2
3
clock_t const start = clock();
merge_sort( /* ... */ );
clock_t const finish = clock();
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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.
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#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
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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?
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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)
Last edited on
Registered users can post here. Sign in or register to post.