Quicksort - reason for equals checks

Question

Many examples on the web about Quicksort (in Java) are close to this:

private void quicksort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];

    while (i <= j) {

      while (numbers[i] < pivot) {
        i++;
      }

      while (numbers[j] > pivot) {
        j--;
      }

      if (i <= j) {
        exchange(i, j);
        i++;
        j--;
      }
    }

    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
}

The thing I'm puzzled about is why there are those equals checks:

1) while (i <= j) instead of while (i < j)

2) if (i <= j) instead of if (i < j)

Are there any edge cases where this equals is crucial? From my understanding if we would have if(i == j), then we would basically exchange the same value with the same value.

Anybody can solve that puzzle for me?

Legere

Could you post a link of one of those online source having code like this? I think you are right that it is quite meaningless to swap with an element itself – Homophile

The snippet from above actually comes from vogella blog. – Legere

Answer 1

Suppose that the condition is replaced by i < j.

Lets see what would happen for an array like:

5,4,3,2,1

The while loop would terminate with i = 2 and j = 2, and we would have overlapping calls to function quicksort and these calls would be:

quicksort(0,2) and quicksort(2,4)

whereas if we do have this condition i<=j the loop would terminate with i = 4 and j = 1 and now we would have calls as:

quicksort(0,1) and quicksort(3,4)

which are the right calls.

So basically you are right there is no point in swapping the same elements but the author of the code must have omitted it to avoid the need for adding an extra condition that you dont need to swap when i equals j

Freeness

I see. It would indeed overlap the "2" index, but it wouldn't break the algorithm in the end would it? Would you tell me what changed you would put to ommit the <= cases from the code above? – Legere

Yes it definitely breaks the algorithm if we have < instead of <= because quicksort partition divides the array into two disjoint subarrays not overlapping subarray. – Freeness

@Legere The only thing that I would do is add the condition for swapping. Meaning I would swap only when i!=j. – Freeness

@Legere The author omitted because it does not affect the correctness and to avoid the need for adding an extra condition. – Freeness