0
$\begingroup$

I found an implementation of Quicksort here, and now I cannot understand why it works with those left and right bounds.

Right now the link above is unavailable due to some problems with their hosting provider.

public class Main {

    public static void main(String[] args) {
        int array[] = new int[] {
                10, 3, 2, 5, 4
        };

        System.out.println("array == " + Arrays.toString(array));
        quickSortModified(array, 0, array.length - 1);
        System.out.println("sorted array == " + Arrays.toString(array));
    }

    private static int partition(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    private static void quickSortModified(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSortModified(arr, left, index - 1);
        if (index + 1 < right)
            // TODO: index + 1 vs index for the bound here.
            quickSortModified(arr, index + 1, right);
    }
}

Why should left be less than index - 1, not just index?

Why should index (not index + 1) be less than right?

For example, on Wikipedia they use index + 1 for the second recursive call.

$\endgroup$
  • $\begingroup$ What have you tried? Have you tried running it by hand on some examples, and then do the same for a modified version of the algorithm the changes made that you have in mind? That's often the best way to get a feeling for an algorithm. Alternatively, you can try proving it correct by finding a loop invariant, though this is often more challenging. $\endgroup$ – D.W. Jun 14 '15 at 6:23
  • $\begingroup$ @D.W., I tried many implementations and got confused with different (as I think) approaches they use. E.g., on en.wikipedia.org/wiki/Quicksort they claim the pivot is in its final position after the partition operation and use the bound [lo, p - 1] and [p + 1, hi]. And the data structure on Wikipedia is not zero-based. @Raphael told me, "The pivot usually ends up in its final position after partitioning." Using index + 1 for the right part, I experienced an ArrayIndexOutOfBoundsException. I just have much information in mess. $\endgroup$ – Maksim Dmitriev Jun 14 '15 at 15:13
  • 1
    $\begingroup$ BTW, there is a bug in the partition function: (left + right) / 2 might overflow in very large arrays. Better to use: left + (right - left) / 2. $\endgroup$ – Branko Dimitrijevic Sep 5 '17 at 21:51
2
$\begingroup$

You haven't given us the complete picture, but in general, if you are going to call quickSort on the slice of the array lo .. hi, then there is only need to do so if lo < hi; otherwise the array has at most one element and doesn't need to be sorted.

$\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.