package random;

import java.util.Random;

public class Quick 
{
	private static Random random = new Random();
	
	/**
	 * Sorts the segment of the given array.
	 * 
	 * @param array
	 * @param left
	 * @param right
	 */
	public static void sort(Integer[] array, int left, int right) 
	{
		int i = left;
		int j = right;
		int h = i + random.nextInt(j - i + 1);
		int pivot = array[h];
		while (i <= j) 
		{
			while (array[i] < pivot)
			{
				i++;
			}
			while (array[j] > pivot)
			{
				j--;
			}
			// array[i] >= pivot && array[j] <= pivot
			if (i <= j) 
			{
				// swap array[i] and array[j]
				int tmp = array[i];
				array[i] = array[j];
				array[j] = tmp;
				i++;
				j--;
			}
		}
		int index = i;
		if (left < index - 1)
		{
			Quick.sort(array, left, index - 1);
		}
		if (index < right)
		{
			Quick.sort(array, index, right);
		}
	}
}