/**

* Quicksort implementation using Hoare partitioning

*

* @author William Fiset, william.alexandre.fiset@gmail.com

**/

import java.util.Random;

public class Quicksort {

public static void quicksort(int[] ar) {

if (ar == null) return;

quicksort(ar, 0, ar.length-1);

}

// Sort interval [lo, hi] inplace recursively

private static void quicksort(int[] ar, int lo, int hi) {

if (lo < hi) {

int splitPoint = partition(ar, lo, hi);

quicksort(ar, lo, splitPoint);

quicksort(ar, splitPoint+1, hi);

}

}

// Performs Hoare partition algorithm for quicksort

private static int partition(int[] ar, int lo, int hi) {

int pivot = ar[lo];

int i = lo-1, j = hi+1;

while(true) {

do { i++; } while(ar[i] < pivot);

do { j--; } while(ar[j] > pivot);

if (i < j) swap(ar, i, j);

else return j;

}

}

// Swap two elements

private static void swap(int[] ar, int i, int j) {

int tmp = ar[i];

ar[i] = ar[j];

ar[j] = tmp;

}

/* TESTING BELOW */

public static void main(String[] args) {

int[] array = {10, 4, 6, 4, 8, -13, 2, 3};

quicksort(array);

System.out.println(java.util.Arrays.toString(array));

runTests();

}

static Random RANDOM = new Random();

public static void runTests() {

final int NUM_TESTS = 1000;

for(int i = 1; i <= NUM_TESTS; i++) {

int[] array = new int[i];

for(int j = 0; j < i; j++) array[j] = randInt(-1000000, +1000000);

int[] arrayCopy = array.clone();

quicksort(array);

java.util.Arrays.sort(arrayCopy);

if (!java.util.Arrays.equals(array, arrayCopy))

System.out.println("ERROR");

}

}

static int randInt(int min, int max) {

return RANDOM.nextInt((max - min) + 1) + min;

}

}