//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 Comparing_sorting_algo
{
    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 swap(int[] A, int i, int j)
    {
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
    }

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

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

    public static void main(String args[])
    {
       int n, value;
       int[] A, B;
	
       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       Selection sort ");
	System.out.println("------------------------------------------------");
	for(n=2000;n<=25600;n=n+1000)
	{
	    long TimeQsort=0;
	    long TimeSelectionSort=0;
		A = new int[n];
	    B = 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];
		
		long start = System.currentTimeMillis();
		Qsort(A,0,A.length-1);
		long stop = System.currentTimeMillis();
		TimeQsort = TimeQsort + stop - start;

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