public class QuickSortAlgo {
	public static void main(String []args)
	{
		int arr[] = {5,2,7,4,1,3,9,6,8};
		System.out.println("Before Sorting>>");
		for(int x : arr)
			System.out.print(x + " ");
		quickSort(arr, 0, arr.length-1);
		System.out.println("\nAfter Sorting>>");
		for(int x : arr)
			System.out.print(x + " ");
	}
	
	private static void quickSort(int []arr, int low, int high)
	{
		if(low < high)
		{
			int p = partition(arr, low, high);
			quickSort(arr, low, p-1);
			quickSort(arr, p+1, high);
		}
	}
	
	private static int partition(int []arr, int low, int high)
	{
		swapper(arr, high, (low+high)/2);
		
		int store = low;
		
		for(int i = low; i < high; i++)
		{
			if(arr[i] <= arr[high])
			{
				swapper(arr, store, i);
				store++;
			}
		}
		
		swapper(arr, store, high);
		return store;
	}
	
	private static void swapper(int []arr, int a, int b)
	{
		int t = arr[a];
		arr[a] = arr[b];
		arr[b] = t;
	}
}