import java.util.ArrayList;
import java.lang.Math;

class RecursionDemo1
{
    /*
    public static long f( int x )
    {
        if( x == 0 )
            return 0;
        else
            return f( x - 1 ) + 2 * x - 1;
    }
     * */
/*
    public static void sort( ArrayList<Integer> items )
    {
        for( int p = 0; p < items.size( ) - 1; p++ )
        {
            // Find index of small item in items[ p....]
            int minIndex = p;
            for( int i = p + 1; i < items.size( ); i++ )
                if( items.get( i ) < items.get( minIndex ) )
                    minIndex = i;

            // Swap minIndex with p
            Integer tmp = items.get( minIndex );
            items.set( minIndex, items.get( p ) );
            items.set( p, tmp );
        }
    }
 * */

    public static void sort( ArrayList<Integer> items )
    {
        if( items.size( ) <= 1 )
            return;

        ArrayList<Integer> smaller = new ArrayList<Integer>( );
        ArrayList<Integer> same    = new ArrayList<Integer>( );
        ArrayList<Integer> larger  = new ArrayList<Integer>( );

        Integer randomItem = items.get( (int) ( Math.random( )  * items.size( ) ) );
        for( Integer i : items )
        {
            if( i < randomItem )
                smaller.add( i );
            else if( i > randomItem )
                larger.add( i );
            else
                same.add( i );
        }

        sort( smaller );   // Recursive call!
        sort( larger );    // Recursive call!

        items.clear( );
        items.addAll( smaller );
        items.addAll( same );
        items.addAll( larger );
    }

    public static int gcd( int lhs, int rhs )
    {
        if( rhs == 0 )
            return lhs;
        
        return gcd( rhs, lhs % rhs );
    }
    
    public static void main( String [ ] args )
    {
        ArrayList<Integer> items = new ArrayList<Integer>( );

        for( int i = 0; i < 25; i++ )
            items.add( (int) ( Math.random( ) * 100 ) );


        System.out.println( items );
        sort( items );
        System.out.println( items );

        System.out.println( gcd( 45000, 35000 ) );
    }
}