import java.math.*;
class quick_sort
{
	static long[] A;
	static int count_swap;
	static int count_comp;
	
	public static void qsort(int l, int r)
	{
		int j = l;
		int i = r;
		int mid = (l + r)/2;
		long x = A[mid];
		do
		{
			while (A[j] < x) 
			{
				j++;	
				count_comp++;	
			}
			while (A[i] > x)
			{
				count_comp++;
				i--;
			}
			
			if (j<= i)
			{
				long temp = A[i];
				A[i] = A[j];
				A[j] = temp;
				j++;
				i--;
				count_swap++;
				count_comp= count_comp + 3;
			}
			
			count_comp++;
		}
		while(j<= i);
		
		if(l<i) qsort(l, i);
		if(j<r) qsort(j, r);
		
		count_comp= count_comp + 3;
	}
	
	public static void main(String[] args)
	{
		A = new long[1000];
				
		for (int r = 0; r<= 999; r++)
		{
			long rand = Math.round(Math.random() * 1000);
			A[r] = rand;
		}
		
		qsort(0, 999);
		
		for(int r = 0; r<= 999; r++)
			System.out.println(A[r]);
			
		System.out.println("Comparisons: "+count_comp);
		System.out.println("Swapings: "+count_swap);
	
	}	
	
	
	
}