public class QuickSort{
	int num[];
	public QuickSort(int a[]){
		num = a;
	}
	
	private int partition(int left, int right, int pivotIndex){
		int pivotValue = num[pivotIndex];
		swap(right, pivotIndex);
		int storeIndex = left;
		for(int i=left; i<right;i++){
			if(num[i]<=pivotValue){
				swap(i, storeIndex);
				storeIndex++;
			}
		}
		swap(storeIndex, num.length-1);
		return storeIndex;
	}
	
	private void swap(int i, int j){
		int temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	
	public void sort(int left, int right){
		if(left<right){
			int pivotIndex=left;
			int newpivotIndex = partition(left, num.length-1, pivotIndex);
			sort(left, newpivotIndex - 1);
			sort(newpivotIndex + 1, right);
		}
	}
	
	public void printNum(){
		for(int i=0; i<num.length; i++){
			System.out.print(num[i] + "  ");
		}
	}
	
	public static void main(String args[]){
		int num[]={3,7,8,5,2,1,9,5,4}; //any arbit array of number, u can change its length
		QuickSort qs = new QuickSort(num);
		qs.sort(0, num.length-1);
		qs.printNum();
	}
}