import DataStructures.*;
import Supporting.*;

// Test all the sorting routines in package DataStructures

public class TestSort
{
    private static final int NUM_ITEMS = 1000;
    private static int theSeed = 1;

    public static void checkSort( MyInteger [ ] a )
    {
        for( int i = 0; i < a.length; i++ )
            if( a[ i ].intValue( ) != i )
                System.out.println( "Error at " + i );
        System.out.println( "Finished checksort" );
    }


    public static void main( String [ ] args )
    {
        MyInteger [ ] a = new MyInteger[ NUM_ITEMS ];
        for( int i = 0; i < a.length; i++ )
            a[ i ] = new MyInteger( i );

        for( theSeed = 0; theSeed < 20; theSeed++ )
        {
            Random.permute( a );
            Sort.insertionSort( a );
            checkSort( a );

            Random.permute( a );
            Sort.heapsort( a );
            checkSort( a );

            Random.permute( a );
            Sort.shellsort( a );
            checkSort( a );

            Random.permute( a );
            Sort.mergeSort( a );
            checkSort( a );

            Random.permute( a );
            Sort.quicksort( a );
            checkSort( a );

            Random.permute( a );
            Sort.quickSelect( a, NUM_ITEMS / 2 );
            System.out.println( a[ NUM_ITEMS / 2 - 1 ].intValue( ) + " is " +
                              NUM_ITEMS / 2 +"th smallest" );
        }
    }
}