class QuickSort {
	
	public static int count = 0;
	
	public static void main(String[] args){
		Integer a[] = new Integer[8];
		for (int i = 0; i < a.length; i++) {
			a[i] = (int) (Math.random()*100);
			System.out.print(a[i] + " ");
		}
		System.out.println();
		
		quicksort(a, 0, a.length - 1);
		
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
		System.out.println("Count: " + count);
	}


	public static void quicksort (Integer[] a, int lo, int hi){
		//  lo is the lower index, hi is the upper index
		//  of the region of array a that is to be sorted
		    int i=lo, j=hi, h;
		    Integer x=a[(lo+hi)/2];
		    count++;
		    //  partition
		    do
		    {    
		        while (a[i].compareTo(x) < 0) {i++; count++;} 
		        while (a[j].compareTo(x) > 0) {j--; count++;}
		        if (i<=j)
		        {
		            h=a[i]; a[i]=a[j]; a[j]=h;
		            i++; j--;
		        }
		    } while (i<=j);
		
		    //  recursion
		    if (lo<j) quicksort(a, lo, j);
		    if (i<hi) quicksort(a, i, hi);
		}
}