I don't understand this quicksort implementation

Question

I have a code for quicksort in C++ that works perfectly for an array of non-unique elements. I'm sure that a lot of people here knows it, but, who does understand it? Let me explain myself better. This is the code:

void quicksort(int a[], int first, int last){
    int i,j;
    int pivot;

    if((last -first + 1) <= 1) return;

    pivot = a[(first+last) / 2];
    i = first;
    j = last;

    while(i <= j){
        while(a[i] < pivot) i++;
        while(a[j] > pivot) j--;

        if(i <= j){
            //SWAP
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            i++;
            j--;
        }
    }

    quicksort(a, first, j);
    quicksort(a,i, last);
}

So, i understand everything but the if on the swap. Can anyone tell me, mathematically, what is the exact case or set of cases where i > j after the two inner whiles? I know specific cases for it, but what is the mathematical (or exact) property of them for happening?

Sorry for the crappy english, and thanks.

PD: Ignore in this case optimizations, or choosing the pivot and all that stuff, please.

Answer 1

If, when starting out, a[i] > pivot (so i is not changed) and a[j] > pivot for all j until a[j] = pivot, the next iteration of the loop will result in a situation where j < i.

To illustrate...

Take the following array:

int a[] = [10, 7, 2, 6, 3];

On the first call of quicksort, with first being 0 and last being 4 (last index in the array), pivot will be a[2] = 2. In the first iteration if the while loop, a[0] > 2, so i is not changed. a[4] > 2, j--, a[3] > 2, j--, a[2] = 2, now we hit the if statement. 0 <= 2, so we swap a[0] and a[2] and execute i++ and j--.

Now the array looks like this:

[2, 7, 10, 6, 3]

with i = 1 and j = 1. a[i] > 2, so i is not changed. a[j] > 2, so j--, j now is 0. a[j] is not greater than 2 (since it is 2), and j stays at 0. Now, we have i = 1 and j = 0, or i > j.

If you notice, the 2 is in it's "sorted" position and does not need to be moved anymore. Also, the pivot was the smallest element in the array. Hope that helps you figure it out.

Answer 2

i and j start at either end of the array until they find a value that is greater than the pivot (a[i]) and less than the pivot (a[j]). When two such values are found they are swapped locations so you end up with an array where after the loop i to the end are greater than the pivot, and the beginning to j is less than the pivot. Than we recurse on these two sub arrays.

i>j when the list is done being divided by the pivot value. i and j have covered every value in the array to make sure it is on the correct side of the pivot. This could happen right in the middle of the array or after only one value being swapped depending on where the pivot value is in the list. The pivot could be the largest or the smallest value, or it could be right in the middle of the list of values.