K&R Qsort example with Pointers and Arrays confusion.

Question

I find it difficult to understand the following snippet of code. I understand the pointer to function mannerism showed, but where I find confusion is in the indicated lines.

void qsort(void **v, int left, int right, int (*comp) (void *, void *))
{
    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 */ [1]
    last = left;                       /* to v[0] */ [2]
    for (i = left + 1; i <= right; i++) /* partition */ [3]
        if ((*comp) (v[i], v[left]) < 0) [4]
            swap(v, ++last, i); [5]
    swap(v, left, last);        /* restore partition elem */ [6]
    qsort(v, left, last - 1); [7]
    qsort(v, last + 1, right);  [8]

}

Can someone explain this routine to me, especially the indicated lines, just tell me what it's doing, because I can't figure this qsort out, the eskimo guide I read whilst reading k&r said that the qsort routine is rubbish, and overly complicated. I just need to understand why it's written like this, because it makes no sense to me.

Thanks, if for nothing, for reading this.

Answer 1

magic useful google keywords: QuickSort

e.g. google:how quicksort works turns up this explanation: http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001a_HowQuicksortWorks.htm among others.

Essentially, the code applies a variation of quicksort to the elements between the left and right boundaries specified.

For the lines you've identified:

1. swap the middle element with the first (left) one. it will become the "pivot".

2. keep track of the boundary between bigger and smaller elements. this is where the pivot belongs.

3. for every element after the first one,
4. if it's smaller than the pivot,

5. move it before the first bigger element.

6. move the pivot back into place.

7. recursively apply qsort to the elements before the pivot. (the smaller ones)

8. recursively apply qsort to the elements after the pivot. (the bigger ones)

Try applying the code yourself to a list of numbers, and see if it makes more sense then....

Answer 2

This is a beautiful piece of code!

First off, it's important that you understand the idea behind quicksort:

1) Take a list of numbers.

2) Pick one, call it X.

3) Make two lists, one of all the numbers smaller than X, and one of all the numbers bigger.

4) Sort the numbers smaller than X. Sort the numbers bigger than X.

The idea is that if we get lucky and pick a good value for X, then the list of numbers smaller than X is the same size as the list of numbers bigger than X. If we start with 2*N+1 numbers, then we get two lists of N numbers. Each time, we hope to divide by two, but we have to sort N numbers. How many times can we divide N by two? That's Log(N). So, we sort N Log(N) times. This is great!

As for how the code works, here's the runthrough, with a little sketch. We'll pick a small array :)

here's our array: [DACBE]

at the start, left=0, pointing to D. right=4, pointing to E.

now, following the code, with your labelling:

[1] swap(v,0,2) [DACBE] -> [CADBE]

we've swapped our chosen value out and put it at the start of the array.

[2] last=0

this is a bit clever... we want to keep a counter so we know which values were greater and which less... you'll see how this progresses

[3] for (i=1;i<=4;i++)

for all the remaining elements in the list...

[4] if ((*comp)(v[i], 'C')<0)

if the value at i is LESS than 'C'...

[5] swap(v,++last,i);

put it at the start of the list!

let's run the code for 3,4,5

i=1:

[CADBE]

if ('A'<'C')

swap('A','A') (AND INCREMENT LAST!)

[CADBE]->[CADBE] (no change)

last=1

i=2:

[CADBE]

if ('D'<'C')

fails. move on.

i=3:

[CADBE]

if ('B'<'C')

swap('B','D') And increment last!

[CADBE] -> [CABDE] (lookit! it's sorting!)

last=2

i=4:

[CABDE]

if ('E'<'C')

fails. move on.

Ok, ace. so that loop gives is [CABDE], last=2 ('B')

Now line [6].... swap(left,last)... that's swap('C','B') [CABDE] -> [BACDE]

Now, the magic of this is... it's partially sorted! BA < C < DE!

So now we sort the sub-lists!!

[7] -> [BA] -> [AB]

so

[BACDE] -> [ABCDE]

[8]-> [DE]->[DE]

so

[ABCDE] -> [ABCDE]

and we're done!

Answer 3

There's a bug in your code, the lines at the end:

qsort(v, left, last - 1); [7]
qsort(v, last + 1, right);  [8]

should be:

qsort(v, left, last - 1, comp); [7]
qsort(v, last + 1, right, comp);  [8]

Or am I missing something?

Furthermore, it's bad style to reuse names of the standard library, especially if the new function has a different signature than the one in the lib. The function qsort of the standard library has this prototype:

 void  qsort(void  *base,  size_t  nel,  size_t  width,   int (*compar)(const void *, const void *));

If your program is a bit bigger (more than one object file) this can give interesting bugs. Imagine another module calling the standard qsort function but as you have redefined it, with a compatible signature, but with a different semantic, you get an unexpected bug.