//This is the program for Quick sort.
//It sorts 15 numbers generated randomly in range 0 to 9999.
//Please go through the method partition and understand it.
//This method does not use any extra array for partitioning.

import java.util.Random;

class Quick_sort
{
    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 main(String args[])
    {
	int[] A = new int[15];
        Random rand = new Random();

        int value;
        for(int i = 0; i<15;i=i+1)
        {
            value = rand.nextInt();
            value = Math.abs(value);
            value = value%10000;
            A[i] = value;
        }
	
	System.out.println("Entries of array A are : ");
        for(int i = 0; i<15;i=i+1)
        {
            System.out.println(A[i]);
        }

        Qsort(A,0,A.length-1);

	System.out.println("Entries of array A after sorting are : ");
        for(int i = 0; i<15;i=i+1)
        {
            System.out.println(A[i]);
        }
    }
}