Created
September 18, 2023 14:30
-
-
Save rmitton/fdf84a56fdfa9a79b051f22c980b8729 to your computer and use it in GitHub Desktop.
A small test harness for timing different sorting algorithms.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment