CODEWITHSUNDEEP
cquicksort
JohnMerlino
JohnMerlino

Reputation: 3928

qsort algorithm in C

I am reading the book "C Programming Language". And in it, it uses its own implementation of qsort:

/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)  /* do nothing if array contains */
        return;     /* fewer than two elements */

    swap(v, left, (left + right)/2);    /* move partition elem */
    last = left;            /* to v[0] */

    for (i = left + 1; i <= right; i++) /* partition */
        if (v[i] < v[left])
            swap(v, ++last, i);

    swap(v, left, last);        /* restore partition elem */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
    int temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

I am trying to understand this using a simple use case, an array containing the following numbers: 0123456789.

The first time swap is invoked, it substitutes the element in middle with first element. In our case, 0 is swapped with 4, so our array now looks like: 4123056789.

Then the confusing part. We set i to be the next element after the first (remember the first element contains the middle value after the swap). Our test keeps running until we hit the last index. We check if the second element is less than the first, if it is we swap them. In our case, i is 1 and we use pre-increment operator which sets last to 1 (since last was initialized to 0). So it seems like when we call swap in this first run of loop, the swap function's i and j argument values will be copied with a value of 1. And hence we aren't even swapping anything. Am I missing something?

Upvotes: 1

Views: 596

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51316

You're not missing anything. For the input you consider, the 2nd through 5th calls to swap() will indeed have equal i and j, resulting in no change to the array.

Although you might be tempted to wrap these calls in an if (i != j) test to "save time", you will probably find that for most inputs this will cause an overall slowdown, because it's an extra test inside the innermost loop, and on randomly ordered inputs it fires rarely (meaning not much time is saved) and unpredictably (meaning branch prediction will get confused).

EDIT: The general principle to take away from this code is that it is simpler and sometimes faster to let a piece code harmlessly do nothing, than to test for the conditions under which it will do nothing and then skip it.

Upvotes: 3

Related Questions