#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;
        }