Three way Quicksort in Java

Question

What do you think about this implementation of quicksort? Is it possible to make it shorter?

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

• 200_success: Are you intentionally shuffling the input as the first step of the sort?
• Guido Celada: yes for providing less chance to the o(n^2) running time probability of happening
• maaartinus: 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.

Answer 1

• 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])