# Three way Quicksort in Java

/**
* 3-way quicksort
* <p/>
* Choose a value an put the greater values to the right, lowers to the
* left, and equals in the center. recursive. O(n^2) but avg O(n log n). Memory: In place
*/
public static void quickSort(int[] array) {
shuffleArray(array);
quickSort(array, 0, array.length - 1);
}

private static void quickSort(int[] array, int lo, int hi) {
if (hi <= lo)
return;

int lowerIndex = lo;
int greaterIndex = hi;
int element = array[lo];
int i = lo;

while (i <= greaterIndex) {
if (array[i] < element)
swap(array, lowerIndex++, i++);
else if (array[i] > element)
swap(array, i, greaterIndex--);
else
i++;
}

quickSort(array, lo, lowerIndex - 1);
quickSort(array, greaterIndex + 1, hi);
}

// O(n)
private static void shuffleArray(int[] ar) {
Random rnd = new Random();
for (int i = ar.length - 1; i > 0; i--) {
int index = rnd.nextInt(i + 1); // random between 0 and i
swap(ar, i, index);
}
}

private static void swap(int[] array, int i, int j) {
int a = array[i];
array[i] = array[j];
array[j] = a;
}

• Are you intentionally shuffling the input as the first step of the sort? Dec 12, 2014 at 20:43
• yes for providing less chance to the o(n^2) running time probability of happening Dec 12, 2014 at 20:44
• There are simpler means... e.g., selecting a single random element and swap it with the future pivot should be equivalent and much faster - this O(n) shuffle suffers from bad memory locality (unlike the quick sort itself) and can take more time than expected. Dec 12, 2014 at 23:28

• i should be initialized to lo + 1 this will reduce the while loop by 1
• you should use braces {} for single if statements. This will make your code less errorprone.
• instead of doing this recursively, you could do is iterativ by adding a while loop with (lo < lowerIndex - 1 && greaterIndex + 1 < hi) as condition.
• for make the if..else if you shoul consider to swap the position of element and array [i] because if you imagine the array, index 0 will be on the left
if (element > array[i])