import java.util.*;
public class QuickSort {
    private int x[],n;
    public QuickSort(int n)
    {
        this.n=n;x=new int[n];
        Scanner src=new Scanner(System.in);
        for(int i=0;i<n;i++)
            x[i]=src.nextInt();
    }
    public void display()
    {
        System.out.println("The Sorted Elements are: ");
        for(int i=0;i<n;i++)
            System.out.print(x[i]+" ");
        System.out.println();
    }
    public int getNum()
    {
        return n;
    }
    public void quickSort(int lb, int ub)
    {
        if(lb<ub)
        {
            int p=partition(lb,ub);
            quickSort(lb,p-1);
            quickSort(p+1,ub);
        }
    }
    public int partition(int lb,int ub)
    {
        int val=x[lb],down=lb+1,up=ub;
        while(down<up)
        {
            while(down<=up&&x[down]<val)
                down++;
            while(x[up]>val)
                up--;
            if(down<up)
            {
                int t=x[down];
                x[down]=x[up];
                x[up]=t;
            }
        }
        x[lb]=x[up];
        x[up]=val;
        return up;
    }

}
class QuickSortExp
{
    public static void main(String args[])
    {
        Scanner src=new Scanner(System.in);
        System.out.println("Enter the no of elements");
        int n=src.nextInt();
        System.out.println();
        QuickSort obj=new QuickSort(n);
        obj.quickSort(0, obj.getNum()-1);
        obj.display();
    }
}

O/P:

Enter the no of elements
10

1
12
34
99
65
34
109
9
43
67
The Sorted Elements are: 
1 9 12 34 34 43 65 67 99 109 
BUILD SUCCESSFUL (total time: 1 minute 33 seconds)
