//This program compares the execution time of 
//Quick sort and Selection sort on different input sizes.
//For each input size, it generate 25 random instances of array
//and calculate the time taken by Quick sort and Selection sort
//on all of them. Note that We execute the two algorithms on same input.
//It uses System.currentTimeMillis() which returns 
//a long integer corresponding to the curent time in milli seconds.
//Compile it and execute it to see the output.
import java.util.Random;

class Three_sorting_algos
{
    //---------------------------------------------------------------------
    //------------Method swap() used by Selection Sort and Quick sort------
    //---------------------------------------------------------------------

    public static void swap(int[] A, int i, int j)
    {
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
    }

    //---------------------------------------------------------------------
    //---------------------Now SELECTION SORT and-------------------------- 
    //-------------the method index_of_smallest_value used by it------------
    //----------------------------------------------------------------------

    public static int index_of_smallest_value(int[] B,int start, int end)
    {
	int index_of_smallest = start;
	int index = start+1;
	for(;index<=end; index=index+1)
	{
	    if(B[index_of_smallest] > B[index])
		index_of_smallest = index;
	}
	return index_of_smallest;
    }

    public static void SelectionSort(int[] B)
    {
	for(int index=0;index<B.length;index=index+1)
        {
	    int index_of_smallest=index_of_smallest_value(B,index,B.length-1);
	    if(index!=index_of_smallest) 
		swap(B,index,index_of_smallest);
	}
    }


    //----------------------------------------------------------------------
    //-----------Now QUICK SORT and the method PARTITION used by it---------
    //----------------------------------------------------------------------

    public static int partition (int[] A, int left, int right)
    {
	int pivot=A[right];

	int NSE_index = left;
	for(int i = left; i<=right-1; i=i+1)
	{
	    if(A[i]<=pivot) 
	    {	
		swap(A,i,NSE_index);
		NSE_index = NSE_index + 1;
	    }
	}
	swap(A,right,NSE_index);
	return NSE_index;
    }

    public static void Qsort(int[] A, int left, int right)
    {
	if(left<right)
	{
	    int mid = partition(A, left, right);
	    Qsort(A,left,mid-1);
	    Qsort(A,mid+1,right);
	}
    }

    //----------------------------------------------------------------------
    //----------- Now MERGE SORT and the method MERGE used by it------------
    //----------------------------------------------------------------------

    public static void merge(int[] A, int left, int mid, int right)
    {
	int[] Temp = new int[right-left+1];
        int i=left; 
        int j=mid+1; 
        int count=0;
        while(i<=mid && j<=right)
	{
	    if(A[i]<A[j]) 
	    {
		Temp[count]=A[i]; 
                i = i+1;
            }
            else 
            {   
                Temp[count]=A[j]; 
                j = j+1;
            }
            count = count+1;
	}        
        while(i<=mid)
	{
	    Temp[count]=A[i]; 
            i = i+1; 
            count = count+1;
	}


        while(j<=right)
	{
	    Temp[count]=A[j]; 
            j = j+1; 
            count = count+1;
	}
	for(i=0; i<count;i=i+1)
	    A[i+left]=Temp[i];
    }

    public static void MergeSort(int[] A, int left, int right)
    {
	if(left!=right)
	{
            int mid = (left+right)/2;
            MergeSort(A, left, mid);
	    MergeSort(A, mid+1, right);
	    merge(A,left,mid,right);
	} 
    }

    //----------------------------------------------------------------------
    //-----------------------Now the main method----------------------------
    //----------------------------------------------------------------------
    public static void main(String args[])
    {
       int n, value;
       int[] A, B, C;
	
       Random rand = new Random();
       System.out.println("The execution time of Quick and Selection sort on");
       System.out.println(" n numbers, when repeated 25 times are :");
	System.out.println("------------------------------------------------");
	System.out.println("n         Quick Sort      Merge Sort     Selection sort ");
	System.out.println("--------------------------------------------------------");
	for(n=1000;n<=20000;n=n+1000)
	{
	    long TimeQsort=0;
	    long TimeMergeSort=0;
	    long TimeSelectionSort=0;

	    A = new int[n];
	    B = new int[n];
            C = new int[n];

	    for(int count=0;count<25;count=count+1)
	    {
		for(int i = 0; i<n;i=i+1)
		{
		    value = rand.nextInt();
		    value = Math.abs(value);
		    value = value%200000000;
		    A[i] = value;
		}
		
		for(int i = 0; i<n;i=i+1)
	        {   
		    B[i] = A[i];
		    C[i] = A[i];
		}

		long start = System.currentTimeMillis();
		Qsort(A,0,A.length-1);
		long stop = System.currentTimeMillis();
		TimeQsort = TimeQsort + stop - start;

		start = System.currentTimeMillis();
		MergeSort(B,0,B.length-1);
		stop = System.currentTimeMillis();
		TimeMergeSort = TimeMergeSort + stop-start;	

		start = System.currentTimeMillis();
		SelectionSort(C);
		stop = System.currentTimeMillis();
		TimeSelectionSort = TimeSelectionSort + stop-start;	
	    }
	    System.out.println(n+"\t\t"+TimeQsort+"\t\t"+TimeMergeSort+"\t\t"+TimeSelectionSort);
	}
    }
}