import java.util.*;

class QuickSort
{
	public static void swap(int[] data, int x, int y)
	{
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}
	
	public static int partition(int[] data, int left, int right)
	{
		int i, j;
		
		i = left;
		for(j = left; j <= right; j++)
		{
			if(data[j] < data[i])
			{
				swap(data, i, j);
				i++;
				swap(data, i, j);	
			}
		}		

		return i;

	}

	public static void recursiveQuickSort(int[] data, int left, int right)
	{
		if (left < right)
		{
			int p = partition(data, left, right);
			recursiveQuickSort(data, left, p-1);
			recursiveQuickSort(data, p+1, right);
		}
	}

	public static void quickSort(int[] data, int n)
	{
		recursiveQuickSort(data, 0, n-1);
	}
	
	public static void main(String[] args)
	{

			// Generate a random integer array of size n
			int[] data;
			int n = 10;
			data = new int[n];
			
			// Random is a java class defined java.util	
			// To learn more about this class see 
			// http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html
			Random rand;
			rand = new Random();

			for(int i = 0; i < n; i++)
				data[i] = rand.nextInt(20);

			for(int i = 0; i < n; i++)
				System.out.print(data[i]+" ");

			System.out.println();

			quickSort(data, n);
			for(int i = 0; i < n; i++)
				System.out.print(data[i]+" ");

			System.out.println();
	}
}