import java.util.*;

public class QuickSort{
	private static Random random = new Random();

	public static void main(String[] args) {
		//int[] array = {8,3,25,2,1,11,14,67,12,5};
		recursiveQuickSort(array, 0, array.length-1);
		System.out.println("The following array should be sorted: ");
		printList(array);
		System.exit(0);
	}

	public static void recursiveQuickSort(int[] list, int first, int last) {
		if(first < last)
		{
			int p = partition(list, first, last);
			printList(list);
			recursiveQuickSort(list, first, p-1);
			recursiveQuickSort(list, p+1, last);
		}
	}

	public static int partition(int[] list, int first, int last) {
		//If you want to implement randomized quick sort
		// just uncomment the next two lines of code
		//int p = first + random.nextInt(last-first+1); 
		//swap(list, first, p);
		int p = first;
		for(int n = p+1; n <= last; n++)
			if(list[n] < list[p])
			{
				swap(list, n, p+1);
				swap(list, p, p+1);
				p++;
			}
		return p;
	}

	private static void swap(int[] list, int index1, int index2) {
		int temp = list[index1];
		list[index1] = list[index2];
		list[index2] = temp;
	}

	protected static void printList(int[] list) {
		for(int n = 0; n < list.length; n++)
			System.out.print(list[n]+" ");
		System.out.println();
	}
}