You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
68 lines
1.7 KiB
C++
68 lines
1.7 KiB
C++
TestSort.cpp - Test program for sorting and selection routines
|
|
|
|
#include <iostream.h>
|
|
#include "Sort.h"
|
|
#include "vector.h"
|
|
#include "Random.h"
|
|
|
|
|
|
void checkSort( const vector<int> & a )
|
|
{
|
|
for( int i = 0; i < a.size( ); i++ )
|
|
if( a[ i ] != i )
|
|
cout << "Error at " << i << endl;
|
|
cout << "Finished checksort" << endl;
|
|
}
|
|
|
|
|
|
void permute( vector<int> & a )
|
|
{
|
|
static Random r;
|
|
|
|
for( int j = 1; j < a.size( ); j++ )
|
|
swap( a[ j ], a[ r.randomInt( 0, j ) ] );
|
|
}
|
|
|
|
|
|
int main( )
|
|
{
|
|
const int NUM_ITEMS = 1000;
|
|
|
|
vector<int> a( NUM_ITEMS );
|
|
for( int i = 0; i < a.size( ); i++ )
|
|
a[ i ] = i;
|
|
|
|
for( int theSeed = 0; theSeed < 20; theSeed++ )
|
|
{
|
|
permute( a );
|
|
insertionSort( a );
|
|
checkSort( a );
|
|
|
|
permute( a );
|
|
heapsort( a );
|
|
checkSort( a );
|
|
|
|
permute( a );
|
|
shellsort( a );
|
|
checkSort( a );
|
|
|
|
permute( a );
|
|
mergeSort( a );
|
|
checkSort( a );
|
|
|
|
permute( a );
|
|
quicksort( a );
|
|
checkSort( a );
|
|
|
|
permute( a );
|
|
largeObjectSort( a );
|
|
checkSort( a );
|
|
|
|
permute( a );
|
|
quickSelect( a, NUM_ITEMS / 2 );
|
|
cout << a[ NUM_ITEMS / 2 - 1 ] << " " << NUM_ITEMS / 2 << endl;
|
|
}
|
|
|
|
return 0;
|
|
}
|