how qsort function from the c programming language works

Question

I'm reading The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie. I've reached chapter 5.6, where he explains the shell sort function using pointers to pointers.

I'm not getting, in the code example he gives, how the qsort function works: from what I understood, ++last will be equal to i?? Are we here swapping the same cell?? It's not making a sense for me.

Here's the code for the two functions:

/* qsort: sort v[left]...V[right] into increasing order */
void qSort(void *v[], int left, int right, funcP comp)
{
    int i, last;

    void swap(void *v[], int, int);

    if (left >= right)             /* do nothing if array contains */
        return;                    /* fewer than two elements */
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left + 1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qSort(v, left, last - 1, comp);
    qSort(v, last + 1, right, comp);
}

}

void swap(void *v[], int i, int j)
{
    void *temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}```

Answer 1

I'm reading The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie. I've reached chapter 5.6, where he explains the shell sort function using pointers to pointers.

Note that the code presented in the question implements the Quicksort algorithm, not Shell sort.

I'm not getting, in the code example he gives, how the qsort function works: from what I understood, ++last will be equal to i?? Are we here swapping the same cell?? It's not making a sense for me.

It may be that ++last is equal to i. In that case, the swap has no net effect. But the first time the comparison function returns a result that is greater than or equal to 0, i will increase without last increasing (take note of the if statement), so that i is equal to last + 2. For the rest of that execution of qsort, i will be at least that far in advance of last, so that ++last is not equal to i. For random data, there will typically be many such events, so that i continues to get farther and farther ahead of last.

Overall, the function rearranges the given array elements into two groups, with all the elements of one less than or equal to all the elements of the other. Then it recurses to do the same job on each of the two groups it just formed.