CODEWITHSUNDEEP
csortingquicksort
Joe
Joe

Reputation: 381

What is the purpose of swap(v, left, (left + right)/2) in K&R's qsort() implementation?

in K&R second edition, section 5.11, page 107:

void qsort(void *v[], int left, int right, int (*comp)(void *, void *)) 
{
    int i, last;
    void swap(void *v[], int, int);
    if (left >= right)
        return;
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left+1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0) /* Here's the function call */
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1, comp);
    qsort(v, last+1, right, comp);
}

However, I am confused about the "swap(v, left, (left + right)/2);". I think it is useless... What's the purpose of this sentence?

Upvotes: 1

Views: 185

Answers (2)

Leorge Takeuchi
Leorge Takeuchi

Reputation: 94

If the sentence is absent, there is no problem if the array V[ ] is random data. However, if V[ ] is sorted data, no swap is encountered, and the variable last is not changed. Thus, last qsort() is equivalent to qsort(v, left+1, right, comp). It means that only one element decreased in recursive call. When comparison number of times in the function is n, comparison needs n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 times to complete. It takes a long time if n is big. Furthermore, if V[ ] is very large, stack overflow error may be encountered. The statement exists to prevent them.
In addition, (left + right) / 2 should be left + (right - left) / 2 to prevent overflow error.

Upvotes: 1

UnknownGosu
UnknownGosu

Reputation: 864

This swap is meant to pick the pivot element and place it at the leftmost position. Then, the variable last is used to count how many elements were greater than the pivot hance belong to the right partition. We don't actually compute the number, though - but only a position of the leftmost element of the right partition. After that, we can safely place the pivot back to where it belongs (exactly to the left of the right partition) - this is what the second swap does - and form the left partition at no cost since we know for sure that all elements that are not the pivot or right partition must belong to the left one.

Still, I strongly recommend to to simply take a piece of paper, write some random integer array and try to walk through the code line by line to see how the partitioning process is performed.

Upvotes: 0

Related Questions