Best Case, O(nlgn)

Worst Case, Ω(n^2)

Memory Complexity, O(lgn)

Ideal case

Worse case

/* Quick Sort
 * @author Lin Chen
 * @version 1.0
 * @since 10.06.2017
 */
import java.util.*;

public class Q
{
	/** Random Quick Sort
	 * @param array integer array
	 * @param p index of left boundary
	 * @param r index of right boundary
	 */
	public static void randomQuicksort(int [] array, int p, int r)
	{
		if(p < r)
		{
			int q = randomPartition(array, p, r);
			quicksort(array, p, q-1);
			quicksort(array, q+1, r);
		}
	}

	/** Quick Sort
	 * @param array integer array
	 * @param p index of left boundary
	 * @param r index of right boundary
	 */
	public static void quicksort(int [] array, int p, int r)
	{
		if(p < r)
		{
			int q = partition(array, p, r);
			quicksort(array, p, q-1);
			quicksort(array, q+1, r);
		}
	}

	/** Random partition, swap random selected element with the last elemtn before paritioning
	 * @param array integer array
	 * @param p index of left boundary
	 * @param r index of right boundary
	 * @return index of pivot
	 */
	public static int randomPartition(int [] array, int p, int r)
	{
		Random ran = new Random();
		int i = ran.nextInt(r-p+1);
		i += p;

		int temp = array[r];
		array[r] = array[i];
		array[i] = temp;

		return partition(array, p, r);
	}

	/** Partition, makes elements on left of pivot are less than pivot, elements on right of pivot are greater than pivot
	 * @param array integer array
	 * @param p index of left boundary
	 * @param r index of right boundary
	 * @return index of pivot
	 */
	public static int partition(int [] array, int p, int r)
	{
		int pivot = array[r];
		int i = p-1;
		for(int j = p; j < r; j++)
		{
			if(array[j] < pivot)
			{
				i++;
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
		int temp = array[i+1];
		array[i+1] = array[r];
		array[r] = temp;

		//System.out.println("Pivot: "+pivot);
		//display(array, p, r);

		return i+1;
	}

	/* Generate a random integer array
	 * @param size array size
	 * @return random array
	 */
	public static int [] getArray(int size)
	{
		int [] array = new int[size];
		Random r = new Random();

		for(int i = 0; i < size; i++)
			array[i] = r.nextInt(100);

		return array;
	}

	public static void display(int [] array, int l, int r)
	{
		for(int i = l; i <= r; i++)
			System.out.printf("%5d", array[i]);
		System.out.println();
	}

	public static void main(String args[])
	{
		int [] array;
		array = getArray(1<<20);

		int [] array2;
		array2 = Arrays.copyOf(array, array.length);

		long start, end;

		//quicksort
		start = System.currentTimeMillis();
		quicksort(array, 0, array.length-1);
		end = System.currentTimeMillis();
	    	System.out.printf("Quick sort time: %10f%n", (end-start)/1000000.0);

		//random quicksort
		start = System.currentTimeMillis();
		randomQuicksort(array2, 0, array2.length-1);
		end = System.currentTimeMillis();
	    	System.out.printf("Random quicksort time: %10f%n", (end-start)/1000000.0);
	}
}