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) {
    quickSort(array, 0, array.length - 1);

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

    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--);

    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;
  • \$\begingroup\$ Are you intentionally shuffling the input as the first step of the sort? \$\endgroup\$ Dec 12, 2014 at 20:43
  • \$\begingroup\$ yes for providing less chance to the o(n^2) running time probability of happening \$\endgroup\$ Dec 12, 2014 at 20:44
  • \$\begingroup\$ 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. \$\endgroup\$
    – maaartinus
    Dec 12, 2014 at 23:28

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.