Timing sort algorithm

Emiliano, 3 Mar 2003

Timing fluctuation can limit the usefulness of timing experiments.

Download source files - 1 Kb

Introduction

Timing fluctuation can limit the usefulness of timing experiments. The idea here is to place the algorithm inside a loop and count the number of iterations between ticks.

The reason for using the time function rather then the clock function is because it can be poorly implemented with the result of "missing ticks", and accumulating this over many loops, it will lead to inaccuracy up to 50%. Using the time function and looping in between ticks will decrease the inaccuracy.

Example

time_t start;
start = time(NULL);

vector<long> iterations;

//reps is the nunber of time that the code will loop
iterations.reserve(reps);
    
while(iterations.size() < reps){
        int count = 0;
        do{
            count++;
            copy(A, A+N, B);
            sort(B, B+N);
            //getting end time
            finish = time(NULL);
            //check that the time has changed before
            //going back into loop and increment count 
        }while(start == finish);
        //inserting count value in the vector that indicates the time we 
        //have looped between a tick during time function
        iterations.push_back(count);
        start = finish;
    }

This can then be repeated for several times, so even if the duration between ticks vary, we can select the most accurate.

Output

The output below shows the average result that has been calculated sorting an array of doubles of length 10000 for 10 times.

Sample Image - timing_sort_algorithm.gif

The result is calculated by retrieving the middle value after the vector has been sorted and dividing it by 1000.0 which will give us the milliseconds.

1000.0/iterations[reps/2]

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Emiliano

	Web Developer
	United Kingdom

No Biography provided

You may also be interested in...

Comments and Discussions

There are several high precision timers that you can use. In 1998 I published this one at codeguru. It uses QueryPerformanceCounter and is rather precise. On my 2.0GHz P4 at work it has an overhead of less than 2 microseconds with a counter frequency of 3.58MHz.

<br />
//<br />
// CElapsed.h - header for the CElapsed class<br />
//<br />
//	Copyright 1998-2003 by Rick York<br />
//	This class is free for use in any and all applications for any purpose.<br />
//<br />
//	To use this class include this header and do the following :<br />
//<br />
//	CElapsed timer;	// instantiate a timer object.<br />
//	timer.Begin();	// start timing<br />
//	...				// your code here<br />
//	double TimeInSeconds = timer.Elapsed();		// obtain elapsed time<br />
//<br />
<br />
#ifndef _CELAPSED_H<br />
#define _CELAPSED_H<br />
#else<br />
#error repeated include of this file<br />
#endif<br />
<br />
<br />
class CElapsed<br />
{<br />
private :<br />
	double  m_Period;<br />
	int     m_Initialized;<br />
	__int64 m_Frequency;<br />
	__int64 m_BeginTime;<br />
<br />
public :<br />
	CElapsed()		// constructor<br />
		{<br />
		// get the frequency of the counter<br />
		m_Initialized = QueryPerformanceFrequency( (LARGE_INTEGER *)&m_Frequency );<br />
		if( ! m_Initialized )<br />
			m_Period = 0.0;<br />
		else<br />
			m_Period = 1.0 / (double)m_Frequency;	// save period of clock<br />
		}<br />
<br />
	BOOL Begin()	// start timing<br />
		{<br />
		if( ! m_Initialized )<br />
			return FALSE;		// error - couldn't get frequency<br />
<br />
		// get the starting counter value<br />
		return QueryPerformanceCounter( (LARGE_INTEGER *)&m_BeginTime );<br />
		}<br />
<br />
	double Elapsed()	// stop timing and get elapsed time in seconds<br />
		{<br />
		// get the ending counter value<br />
		__int64 endtime;<br />
		QueryPerformanceCounter( (LARGE_INTEGER *)&endtime );<br />
<br />
		// determine the elapsed counts<br />
		__int64 elapsed = endtime - m_BeginTime;<br />
<br />
		// convert counts to time in seconds and return it<br />
		return (double)elapsed * m_Period;<br />
		}<br />
<br />
	BOOL Available()	// returns true if the perf counter is available<br />
		{ return m_Initialized; }<br />
<br />
	__int64 GetFreq()	// return perf counter frequency as large int<br />
		{ return m_Frequency; }<br />
};<br />
<br />