#include <iostream>
#include "Sort.h"
#include <vector>
#include "Random.h"

using namespace std;

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 );
        insertionSort( a.begin( ), a.end( ) );
        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;
}