/* 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); } }