import java.io.*;
import java.util.*;
    
//-------------------------------------------------------------------
// This program implements 4 sorting algorithms : bubble, 
// insertion, selection and quick.  It counts the number of
// loops, number of comparisons, number of swaps each of 
// these algorithms perform on input with different properties
// (sorted, inverse sorted, and random).
//  
// The class hierarchy are as follows :
// - SortMain  - the class with the main() method
// - Sorter               // abstract sorting class, for sorting.
//   +- BubbleSorter      // implments bubble sort
//   +- QuickSorter       // implments quick sort
//   +- InsertionSorter   // implments insertion sort
//   +- SelectionSorter   // implments selection sort
// - TestGenerator  - abstract class for generating test arrays.
//   +- RandomGenerator   // generates a random array
//   +- SortedGenerator   // generates a sorted array
//   +- InverseSortedGenerator  // generates an inverse sorted array.
//
// TODO : Add more comments to the sort implementations.
//--------------------------------------------------------------------

public class SortMain
{
    // The size of the array to sort.  Modify this value to change the
    // lenght of the array.

    final static int DATA_SIZE = 100;
    
    public static void main(String[] args) throws IOException
    {
        // An array of array generators.  If you want to add a new type
        // of array, simple add the generator here.

        TestGenerator gen[] = {
            new RandomGenerator(0),
            new SortedGenerator(0),
            new InverseSortedGenerator(0)
        };
        
        // An array of Sorter. If you want to add a new sorting algorithm,
        // simply add the sorter here.

        Sorter sorter[] = {
            new QuickSorter (),
            new InsertionSorter (),
            new SelectionSorter (),
            new BubbleSorter ()
        };

        // Loop through all generator, and all sorting algorithm, and
        // print out the statistics.

        System.out.println("Array Length : " + DATA_SIZE + "\n");
        for (int i = 0; i < gen.length; i++)
        {
            for (int j = 0; j < sorter.length; j++)
            {
                sorter[j].init(gen[i].generate(DATA_SIZE));
                sorter[j].sort();
                System.out.println(sorter[j].describe() + "\t" + 
                           gen[i].describe() + "\t" + sorter[j].stats());
            }
            System.out.println();
        }
        
        System.in.read();
    }
}


//----------------------------------------------------------
// Sorter
// 
// An abstraction that contains an array.  We can sort the 
// array.  There is a toString function that can print out 
// the elements in the array.  We also keep tracks of the
// number of comparison, number of exchanges, and number of 
// loops.  These statistic can be accessed by the stats()
// method. 
//----------------------------------------------------------

abstract class Sorter
{
    int b[];
    int numOfComparisons;
    int numOfLoops;
    int numOfExchanges;
    String description;  // name of this sorting algorithm
    
    //------------------------------------------------------
    // Constructor for Sorter
    // This constructor takes in a description that describe
    // this sorting method.
    //------------------------------------------------------

    public Sorter(String description)
    {
        this.description = new String(description);
    }
    

    //------------------------------------------------------
    // init()
    //
    // input : an array of integer.
    // Initialized the sorter with an array to be sorted. 
    //------------------------------------------------------

    public void init(int b[])
    {

        numOfComparisons = 0;
        numOfLoops = 0;
        numOfExchanges = 0;

        // make a copy of the array.
        this.b = new int[b.length];
        for (int i = 0; i < b.length; i++)
        {
            this.b[i] = b[i];
        }
    }   
    

    //------------------------------------------------------
    // describe()
    //
    // Return the description of this Sorter.
    //------------------------------------------------------

    public String describe()
    {
        return description;
    }
    

    //------------------------------------------------------
    // stats()
    //
    // Return the stats of this sorter as a string. 
    //------------------------------------------------------

    public String stats()
    {
        return numOfComparisons + "\t" + numOfLoops + "\t" 
            + numOfExchanges;
    }
    

    //------------------------------------------------------
    // toString()
    //
    // Return the elements of this array as a string.
    //------------------------------------------------------

    public String toString()
    {
        String n = "";
        for (int i = 0; i < b.length; i++)
        {
            n = n + b[i] + "\t";
        }
        return n;
    }   


    //------------------------------------------------------
    // swap()
    //
    // input : two indices of array b : i, j
    // Swap the element b[i] and b[j] in the array b.
    //------------------------------------------------------

    protected void swap(int i, int j)
    {
        int temp = b[i];
        b[i] = b[j];
        b[j] = temp;
    }

    abstract public void sort();
}


//-----------------------------------------------
// BubbleSorter
// 
// This subclass of Sorter implements the sort
// method using BubbleSort.
//-----------------------------------------------

class BubbleSorter extends Sorter
{
    public BubbleSorter()
    {
        super("Bubble Sort");
    }
    
    
    public void sort()
    {
        for (int i = 0; i < b.length; i++)
        {
            for (int j = 0; j < b.length - 1 - i; j++)
            {
                numOfLoops++;
                numOfComparisons++;
                
                if (b[j] > b[j+1])
                {
                    numOfExchanges++;
                    // swap b[j] and b[j+1]
                    swap(i, j);
                }
            }
        }
    }
}


//-----------------------------------------------
// SelectionSorter
// 
// This subclass of Sorter implements the sort
// method using selection sort.
//-----------------------------------------------

class SelectionSorter extends Sorter
{
    public SelectionSorter()
    {
        super("Selection Sort");
    }
    
    
    public void sort()
    {
        for (int k = 0; k < b.length-1; k++)
        { 
            // Find min so that b[min] is the minimum of b[k..b.length-1]   
            int min = k; 
            for (int h = k+1; h < b.length; h++)
            {
                numOfLoops++;
                numOfComparisons++;
                if (b[h] < b[min])
                    min = h; 
            }
            
            numOfExchanges++;
            // Swap b[k] with b[min] 
            swap(k, min);
        }
    }
}


//-----------------------------------------------
// InsertionSorter
//
// This subclass of Sorter implements the sort
// method using insertion sort.
//-----------------------------------------------

class InsertionSorter extends Sorter
{
    public InsertionSorter()
    {
        super("Insertion Sort");
    }
    

    public void sort()
    {
        for (int k= 0; k < b.length; k++) 
        {
            // Place b[k] in its sorted position in b[0..k] 
            int temp = b[k]; //Save b[k] in temp 
            int h = k; 
            
            // Inv: b[0..k] is sorted except for position b[h], temp <= b[h+1..k] 
            numOfExchanges++;
            numOfComparisons++;
            for (h = k; (h != 0) && b[h-1]>=temp; h--)
            {
                numOfComparisons++;
                numOfLoops++;
                numOfExchanges++;
                b[h]= b[h-1];
            }
            
            // Note: {b[0..h-1] <= temp <= b[h+1..k]} 
            b[h] = temp;
        } 
    }
}


//-----------------------------------------------
// QuickSorter
//
// This subclass of Sorter implements the sort
// method using quick sort.
//-----------------------------------------------

class QuickSorter extends Sorter
{
    //------------------------------------------------------
    // The class SubTask encapsulates a sub-array that we
    // want to sort.  It simply contains the indices of the
    // first element and the last element of this sub-array.
    //------------------------------------------------------
    class SubTask 
    {
        int first;
        int last;
        public SubTask(int first, int last)
        {
            this.first = first;
            this.last = last;
        }
    }
    

    public QuickSorter()
    {
        super("Quick Sort");
    }
    

    public int partition (int first, int last) 
    { 
        int pivot = b[first];
        int i = first;
        int j = last; 
        while (i <= j) 
        { 
            numOfLoops++;
            numOfComparisons++;
            
            if (b[i] <= pivot) 
            {   
                i++; 
            }
            else 
            {
                numOfComparisons++;
                if (b[j] > pivot) 
                    j--; 
            
                else 
                {   
                    numOfExchanges++;
                    //Swap b[i] and b[j] 
                    swap(i, j);
                }
            }
        }
        numOfExchanges++;
        swap(first, j);
        
        return j; 
    }

    public void quickSort(int first, int last)
    {
        SubTask c[] = new SubTask[last + 1 - first];
        c[0] = new SubTask(first, last);
        
        int i = 1;
        while ( i > 0 ) 
        {
            numOfLoops++;
            i--;
            int f = c[i].first;
            int l = c[i].last;
            
            if  (l - f == 1) 
            {
                numOfComparisons++;
                if (b[f] > b[l]) 
                {
                    numOfExchanges++;
                    swap(f, l);
                }
            }
            else if (l - f > 1) 
            {
                int j = partition(f, l);
                c[i++] = new SubTask(f, j - 1);
                c[i++] = new SubTask(j+1, l);
            }
        }
    }


    public void sort()
    {
        quickSort(0, b.length - 1);
    }
    
}


//------------------------------------------------------
// TestGenerator
// 
// This class encapsulates a test generator that can
// generate an array of random numbers with a certain
// properties.  The concrete subclass of TestGenerator
// should implement the function generate() that 
// generate an array.
//------------------------------------------------------

abstract class TestGenerator
{
    Random r;
    String description;
    
    public TestGenerator(int seed, String description)
    {
        this.description = new String(description);
        r = new Random(seed);
    }
    
    public String describe()
    {
        return description;
    }
    
    public abstract int [] generate(int numOfElem);
}


//------------------------------------------------------
// RandomGenerator
// 
// This subclass of TestGenerator generates an array
// of random numbers, between -999 and 999.
//------------------------------------------------------

class RandomGenerator extends TestGenerator
{
    public RandomGenerator(int seed)
    {
        super(seed, "Random   ");
    }
    
    public int [] generate(int numOfElem)
    {
        int b[] = new int[numOfElem];
        for (int i = 0; i < numOfElem; i++)
        {
            b[i] = r.nextInt()%1000;
        }
        return b;
    }
}


//------------------------------------------------------
// SortedGenerator
// 
// This subclass of TestGenerator generates an array
// that are sorted in increasing order.
//------------------------------------------------------

class SortedGenerator extends TestGenerator
{
    public SortedGenerator(int seed)
    {
        super(seed, "Sorted   ");
    }
    
    public int [] generate(int numOfElem)
    {
        int b[] = new int[numOfElem];
        b[0] = r.nextInt()%1000;
        for (int i = 1; i < numOfElem; i++)
        {
            int delta = r.nextInt()%10;
            // make sure that the increment is positive.
            if (delta < 0)
                delta = -delta;
            b[i] = b[i-1] + delta;
        }
        return b; 
    }
}


//------------------------------------------------------
// InverseSortedGenerator
// 
// This subclass of TestGenerator generates an array
// that are sorted in decreasing order.
//------------------------------------------------------

class InverseSortedGenerator extends TestGenerator
{
    public InverseSortedGenerator(int seed)
    {
        super(seed, "InvSorted");
    }
    
    public int [] generate(int numOfElem)
    {
        int b[] = new int[numOfElem];
        b[0] = r.nextInt()%1000;
        for (int i = 1; i < numOfElem; i++)
        {
            int delta = r.nextInt()%10;
            // make sure that the increment is positive.
            if (delta < 0)
                delta = -delta;
            b[i] = b[i-1] - delta; 
        }
        return b; 
    }
}