A small test harness for timing different sorting algorithms.

sort_analysis.cpp

// A small test harness for timing different sorting algorithms.
// Prints a graph as a .svg file to stdout.
//
// sort_analysis.exe > output.svg
//

#include <stdio.h>
#include <windows.h>
#include <assert.h>
#include <math.h>
#include <algorithm>

// Range and granularity of values of 'n' we'll be testing:
#define TEST_RANGE  1000000
#define TEST_STEP   10000

// Output image size:
#define IMAGE_WIDTH		800
#define IMAGE_HEIGHT	400

// Temporary buffers:
unsigned *data, *original, *reference;

// ShellSort (v1 original)
//------------------------------------------------------------------------------
template < class T, class COMPARE >
void ShellSort_v1( T* begin, T* end, const COMPARE& compare )
{
	const size_t numItems = (size_t)( end - begin );
	size_t increment = 3;
	while ( increment > 0 )
	{
		for ( size_t i = 0; i < numItems; i++ )
		{
			size_t j = i;
			T temp( begin[i] );
			while ( ( j >= increment ) && ( compare( temp, begin[j - increment] ) ) )
			{
				begin[j] = begin[j - increment];
				j = j - increment;
			}
			begin[j] = temp;
		}
		if ( increment / 2 != 0 )
		{
			increment = increment / 2;
		}
		else if ( increment == 1 )
		{
			increment = 0;
		}
		else
		{
			increment = 1;
		}
	}
}

template<class T> struct RemoveReference { using type = T; };
template<class T> struct RemoveReference<T&> { using type = T; };
template<class T> struct RemoveReference<T&&> { using type = T; };
template<class T> using RemoveReferenceT = typename RemoveReference<T>::type;
#define Move( x ) static_cast<RemoveReferenceT<decltype(x)> &&>( x )

// ShellSort (improved v2)
//------------------------------------------------------------------------------
template < class T, class COMPARE >
void ShellSort_v2( T* begin, T* end, const COMPARE& compare )
{
	// Ciura, Marcin (2001). "Best Increments for the Average Case of Shellsort".
	static const size_t gaps[] = { 510774, 227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1 };

	const size_t numItems = (size_t)( end - begin );
	for ( const size_t increment : gaps )
	{
		if ( increment > numItems )
		{
			continue;
		}

		for ( size_t i = 0; i < numItems; i++ )
		{
			size_t j = i;
			T temp( Move( begin[i] ) );
			while ( ( j >= increment ) && ( compare( temp, begin[j - increment] ) ) )
			{
				begin[j] = Move( begin[j - increment] );
				j = j - increment;
			}
			begin[j] = Move( temp );
		}
	}
}

template < class T >
static inline void SortSwap( T& a, T& b ) { T tmp( a ); a = b; b = tmp; }
static inline size_t SortMin( size_t a, size_t b ) { return a < b ? a : b; }

// QuickSort
//------------------------------------------------------------------------------
template < class T, class COMPARE >
void QuickSort( T* begin, T* end, const COMPARE& less )
{
	struct Stack { T* arr, * end; } stack[64], range = { begin, end };
	int depth = 0;

	for ( ;;)
	{
		// Sort small runs with O(n^2) insertion sort, large with O(log n) quick sort.
		size_t count = range.end - range.arr;
		if ( count <= 16 || depth >= 63 )
		{
			for ( size_t i = 1; i < count; i++ )
			{
				T tmp( range.arr[i] );
				size_t j = i;
				while ( j > 0 && less( tmp, range.arr[j - 1] ) )
				{
					range.arr[j] = range.arr[j - 1];
					j--;
				}
				range.arr[j] = tmp;
			}

			// Pop new range off stack.
			if ( depth <= 0 )
				break;
			range = stack[--depth];
		}
		else {
			// Pick median-of-3 as pivot.
			T* a = range.arr, * b = range.arr + ( count >> 1 ), * c = range.end - 1;
			if ( less( *c, *a ) ) SortSwap( *a, *c );
			if ( less( *b, *c ) ) SortSwap( *c, *b );
			if ( less( *c, *a ) ) SortSwap( *a, *c );
			T pivot( *c );

			// Partition into (eq, lt, gt, eq). (Bentley/McIlroy, "Engineering a Sort Function", 1993)
			size_t i = 0, j = count - 1, ieq = 0, jeq = count - 1;
			for ( ;;)
			{
				while ( i <= j && !less( pivot, range.arr[i] ) )
				{
					if ( !less( range.arr[i], pivot ) )
						SortSwap( range.arr[ieq++], range.arr[i] );
					i++;
				}
				while ( j >= i && !less( range.arr[j], pivot ) )
				{
					if ( !less( pivot, range.arr[j] ) )
						SortSwap( range.arr[jeq--], range.arr[j] );
					j--;
				}
				if ( i > j )
					break;
				SortSwap( range.arr[i++], range.arr[j--] );
			}

			// Move elements equal to the pivot back into the middle.
			size_t s = SortMin( ieq, i - ieq );
			for ( size_t l = 0, h = i - s; s; s-- )
				SortSwap( range.arr[l++], range.arr[h++] );
			s = SortMin( jeq - j, count - 1 - jeq );
			for ( size_t l = i, h = count - s; s; s-- )
				SortSwap( range.arr[l++], range.arr[h++] );

			// Save one half for later and recurse into the other.
			stack[depth++] = { range.arr + count - ( jeq - j ), range.end };
			range = { range.arr, range.arr + ( i - ieq ) };
		}
	}
}

//------------------------------------------------------------------------------

bool cmp( unsigned a, unsigned b )
{
	return a < b;
}
int qsortcmp( const void* a, const void* b )
{
	unsigned ua = *(unsigned*)a, ub = *(unsigned*)b;
	if ( ua < ub ) return -1;
	if ( ua > ub ) return +1;
	return 0;
}

double time_sort( int algo, int n )
{
	// Initialize a fresh random dataset.
	for ( size_t i = 0; i < n; i++ )
		data[i] = original[i] = reference[i] = rand() & 0xffff; // limit to 16-bit numbers to ensure duplicates will exist

	// Sort using a known reference algorithm first to check against later.
	std::sort( reference, reference + n );

	// Time it.
	LARGE_INTEGER before, after, freq;
	QueryPerformanceCounter( &before );
	switch ( algo )
	{
	case 0: memset( data, 0, n * sizeof( data[0] ) ); break; // just as a control group
	case 1: ShellSort_v1( data, data + n, cmp ); break;
	case 2: ShellSort_v2( data, data + n, cmp ); break;
	case 3: QuickSort( data, data + n, cmp ); break;
	case 4: qsort( data, n, sizeof( data[0] ), qsortcmp ); break;
	case 5: std::sort( data, data + n ); break;
	}
	QueryPerformanceCounter( &after );
	QueryPerformanceFrequency( &freq );

	double duration = ( after.QuadPart - before.QuadPart ) / (double)freq.QuadPart;

	// Compare against reference sort to check for correctness.
	if ( algo != 0 )
	{
		for ( size_t i = 0; i < n; i++ )
		{
			if ( data[i] != reference[i] )
			{
				fprintf( stderr, "**** MISMATCH at %zu\n", i );
				abort();
			}
		}
	}

	return duration;
}

int main( int argc, char* argv[] )
{
	data = new unsigned[TEST_RANGE];
	original = new unsigned[TEST_RANGE];
	reference = new unsigned[TEST_RANGE];

	const char* colors[] = { "gray", "crimson", "yellow", "lawngreen", "blue", "magenta" };
	const char* labels[] = { "memset", "ShellSort[v1]", "ShellSort[v2]", "QuickSort", "qsort", "std::sort" };

	printf( "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n" );
	printf( "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n" );
	printf( "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"%i\" height=\"%i\">\n", IMAGE_WIDTH, IMAGE_HEIGHT );

	printf( "<rect width=\"100%%\" height=\"100%%\" fill=\"silver\"/>\n" );

	for ( int algo = 0; algo < 6; algo++ )
	{
		printf( "<polyline style=\"fill:none;stroke:%s;stroke-width:2\" points=\"", colors[algo] );

		double duration = 0;
		for ( int n = 0; n <= TEST_RANGE; n += TEST_STEP )
		{
			// Time each sort with different values of 'n':
			duration = time_sort( algo, n );

			double y = ( duration < 1.0 ) ? ( duration / 2 ) : ( log( duration ) / 8 + 0.5 ); // switch from linear to logarithmic as duration increases past 1sec.
			printf( "%f,%f \n", (double)n * (double)IMAGE_WIDTH / (double)TEST_RANGE, IMAGE_HEIGHT - 20.0f - y * IMAGE_HEIGHT );
			fprintf( stderr, "%s, n=%i, %f secs\n", labels[algo], n, duration );
		}

		printf( "\"/>\n" );
		printf( "<text x=\"%f\" y=\"%f\" font-size=\"12\" fill=\"%s\">%s (%.3f secs)</text>\n",
			10.0f + algo * IMAGE_WIDTH / 6, IMAGE_HEIGHT - 5.0f, colors[algo], labels[algo], duration );
	}

	printf( "</svg>\n" );

	return 0;
}