import java.util.*;

/**
 * QuickSort
 * 
 * @author Andrei Mosso Mendoza
 * @version 0.1
 */
public class QuickSort {

	public static void main(String args[]) {
	
		Random r = new Random();
		int arr[] = new int[1000000];
		int arr1[] = new int[1000000];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = r.nextInt(arr.length * 10);
			arr1[i] = arr[i];
		}
		long ti = 0;
		
		ti = System.currentTimeMillis();
		Arrays.sort(arr1);
		System.out.println("*** " + (System.currentTimeMillis() - ti));
		
		ti = System.currentTimeMillis();
		quickSort(arr);
		System.out.println("*** " + (System.currentTimeMillis() - ti));
	}
	
	public static void quickSort(int arr[]) {
	
		qksort(arr, 0, arr.length - 1);
	}
	
	private static void qksort(int arr[], int left, int right) {
	
		if (right - left >= 1) {
			int i = split(arr, left, right);
			qksort(arr, left, i - 1);
			qksort(arr, i + 1, right);
		}
	}
	
	private static int split(int arr[], int left, int right) {
	
		int i = left;
		int v = random(arr, left, right);
		swap(arr, left, v);
		
		for (int j = left; j <= right; j++) {
			if (arr[j] < arr[i]) {
				swap(arr, i, j);
				i++;
				swap(arr, i, j);
			}
		}
		
		return i;
	}
	
	private static void swap(int arr[], int i, int j) {
	
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	private static int random(int arr[], int left, int right) {
	
		Random r = new Random();
		return r.nextInt(right - left + 1) + left;
	}
	
	private static void display(int arr[]) {
	
		System.out.print("[");
		for (int i = 0; i < arr.length - 1; i++) {
			System.out.print(arr[i] + ", ");
		}
		System.out.println(arr[arr.length - 1] + "]");
	}
}