4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Are you intentionally shuffling the input as the first step of the sort? \$\endgroup\$ – 200_success Dec 12 '14 at 20:43
  • \$\begingroup\$ yes for providing less chance to the o(n^2) running time probability of happening \$\endgroup\$ – Guido Celada Dec 12 '14 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 '14 at 23:28
1
\$\begingroup\$
  • 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])
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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