1

##### C/C++ & Visual C++ / Re: sorts ... template merge sort and quick sorts compared, template insert sort

« Last post by**David**on

*November 10, 2018, 07:12:55 AM*»

Code: [Select]

`// several 'definitions' follow ... //`

template< typename T >

void print( const T ary[], size_t size )

{

for( size_t i = 0; i < size; ++i ) cout << setw(8) << ary[i];

if( size ) std::cout << std::endl;

}

template< typename T >

void print( const vector < T >& v )

{

for( size_t i = 0; i < v.size(); ++i ) cout << setw(8) << v[i];

if( v.size() ) cout << endl;

}

template< typename T >

bool isSorted( const T* ary, size_t size, bool a )

{

if( a ) // ascending

{

for( int i = size-1; i > 0; --i )

{

if( ary[i-1] > ary[i] )

{

#if myDebug

cout << ary[i-1] << ", " << ary[i] << endl;

pause();

#endif

return false;

}

}

}

else // descending //

{

for( int i = size-1; i > 0; --i )

{

if( ary[i-1] < ary[i] )

{

#if myDebug

cout << ary[i-1] << ", " << ary[i] << endl;

pause();

#endif

return false;

}

}

}

// else ...

return true;

}

template< typename T >

bool isSorted( const vector< T >& ary, bool a )

{

if( a )

{

for( int i = ary.size()-1 ; i > 0 ; --i )

{

if( ary[i-1] > ary[i] )

{

#if myDebug

cout << ary[i-1] << ", " << ary[i] << endl;

pause();

#endif

return false;

}

}

}

else

{

for( int i = ary.size()-1 ; i > 0 ; --i )

{

if( ary[i-1] < ary[i] )

{

#if myDebug

cout << ary[i-1] << ", " << ary[i] << endl;

pause();

#endif

return false;

}

}

}

// else ...

return true;

}

bool isSortedCstrs( char** ary, size_t size, bool a )

{

if( a ) // ascending

{

for( int i = size-1; i > 0; --i )

{

if( strcmp( ary[i-1], ary[i] ) > 0 )

{

#if myDebug

cout << "'" << ary[i-1] << "', '" << ary[i] << "'\n";

pause();

#endif

return false;

}

}

}

else // descending //

{

for( int i = size-1; i > 0; --i )

{

if( strcmp( ary[i-1], ary[i] ) < 0 )

{

#if myDebug

cout << "'" << ary[i-1] << "', '" << ary[i] << "'\n";

pause();

#endif

return false;

}

}

}

// else ...

return true;

}

bool fillFromFile( const char* fname, Words& wds, std::map< string, int >& myPairs )

{

ifstream fin( fname );

if( fin.is_open() )

{

string line, word;

while( getline( fin, line ) )

{

istringstream iss(line);

while( iss >> word )

{

if( word[0] == '[' ) continue;

toAllCaps( word );

unsigned i = 0, len = word.size();

while( i < len && ('A' <= word[i] && word[i] <= 'Z') )

++i ;

if( i < len )

word.erase(i);

if( !word.size() ) continue;

if( myPairs.count( word ) ) ++ myPairs[word] ;

else myPairs[word] = 1;

wds.push_back( word );

}

}

fin.close();

return true;

}

// else

std::cout << "\nThere was a problem opening file "

<< fname << "\n\n";

return false;

}

void toAllCaps( string& str )

{

unsigned i = 0, len = str.size();

while( i < len ) {

str[i] = toupper(str[i]);

++ i;

}

}

void pause( const string& msg )

{

cout << msg << flush;

string dummyLine;

getline( cin, dummyLine );

}

// typical output to first part ... //

/*

There were 300160 words read from file: 'Psalms119times128.txt'

495 of which were unique ...

Re. the vector 'myWords' and the array 'ary' ...

Time to msort vector was 0.499 seconds.

Time to msort vector (passing in functor) was 0.499 seconds.

Time to msort vector (down, passing in functor) was 0.374 seconds.

Time to msort array was 0.515 seconds.

Time to msort array (passing in functor) was 0.523 seconds.

Time to msort array (down, passing in functor) was 0.43 seconds.

Time to qSort2 vector was 0.327 seconds.

Time to qSort2 vector (passing in functor) was 0.358 seconds.

Time to qSort2 vector (down, passing in functor) was 0.297 seconds.

Time to qSort2 array was 0.296 seconds.

Time to qSort2 array (passing in functor) was 0.327 seconds.

Time to qSort2 array (down, passing in functor) was 0.281 seconds.

Time to qSort vector was 0.265 seconds.

Time to qSort vector (passing in functor) was 0.265 seconds.

Time to qSort vector (down, passing in functor) was 0.218 seconds.

Time to qsort array of string was 0.124 seconds.

Time to qsort array of string (down) was 0.094 seconds.

Time to qsort ragged array was 0.093 seconds.

Time to qsort ragged array (down) was 0.031 seconds.

Time to C++ library sort vector was 0.156 seconds.

Time to C++ library sort vector (passing in compare function) was 0.171 seconds.

Time to C++ library sort vector (down, passing in compare function) was 0.125 se

conds.

Time to shellsort vector was 0.608 seconds.

Time to shellsort vector (passing in functor) was 0.558 seconds.

Time to shellsort vector (down, passing in functor) was 0.421 seconds.

Press 'Enter' to continue and see the (word, count) pairs ...

The word: 'A' occured 1536 times =? 1536 times.

The word: 'ABHOR' occured 128 times =? 128 times.

The word: 'ABIDETH' occured 128 times =? 128 times.

The word: 'ABOVE' occured 256 times =? 256 times.

The word: 'ACCEPT' occured 128 times =? 128 times.

The word: 'ACCORDING' occured 2304 times =? 2304 times.

The word: 'AFFLICTED' occured 512 times =? 512 times.

The word: 'AFFLICTION' occured 384 times =? 384 times.

The word: 'AFRAID' occured 128 times =? 128 times.

The word: 'AFTER' occured 512 times =? 512 times.

The word: 'AGAINST' occured 384 times =? 384 times.

The word: 'AIN' occured 128 times =? 128 times.

The word: 'ALEPH' occured 128 times =? 128 times.

The word: 'ALL' occured 2304 times =? 2304 times.

The word: 'ALMOST' occured 128 times =? 128 times.

The word: 'ALSO' occured 768 times =? 768 times.

The word: 'ALWAY' occured 128 times =? 128 times.

The word: 'AM' occured 384 times =? 384 times.

The word: 'AN' occured 384 times =? 384 times.

The word: 'ANCIENTS' occured 128 times =? 128 times.

Press 'Enter' to continue ...

The word: 'AND' occured 8064 times =? 8064 times.

The word: 'ANGUISH' occured 128 times =? 128 times.

The word: 'ANSWER' occured 128 times =? 128 times.

The word: 'ANY' occured 128 times =? 128 times.

The word: 'ARE' occured 384 times =? 384 times.

The word: 'ART' occured 128 times =? 128 times.

The word: 'AS' occured 896 times =? 896 times.

The word: 'ASHAMED' occured 640 times =? 640 times.

The word: 'ASTRAY' occured 256 times =? 256 times.

The word: 'AT' occured 512 times =? 512 times.

The word: 'AWAY' occured 384 times =? 384 times.

The word: 'AWE' occured 128 times =? 128 times.

The word: 'BANDS' occured 128 times =? 128 times.

The word: 'BE' occured 1664 times =? 1664 times.

The word: 'BECAUSE' occured 1152 times =? 1152 times.

The word: 'BECOME' occured 128 times =? 128 times.

The word: 'BEEN' occured 384 times =? 384 times.

The word: 'BEFORE' occured 640 times =? 640 times.

The word: 'BEGINNING' occured 128 times =? 128 times.

The word: 'BEHELD' occured 128 times =? 128 times.

Press 'Enter' to continue ...

*/