Programming

this is the code in K & R ritchie

void qsort(int v[], int left, int right){
int i, last;
void swap(int v[], int i, int j);

if(left >= right)
return;
swap(v, left, (left + right)/2);
last = left;
for(i = left + 1; i <= right; i++)
if(v[i] < v[left])
swap(v, ++last,i); swap(v, left, last);
qsort(v , left, last - 1);
qsort(v, last - 1, right);
}

the highlighted portion does not make sense to me at the first go, b'cos it is trying to swap the same element. i find (i & last ) have the same value when swap is called in the for loop for the first time, plz explain....

thanks in advance

PLEASE put code in code tags! They are wonderful, magical things that make it possible to read your code without one's eyes spontaneously bleeding.

Code:

void qsort(int v[], int left, int right){
           int i, last;
           void swap(int v[], int i, int j);

           if(left >= right)
                 return;
           swap(v, left, (left + right)/2);
           last = left;
           for(i = left + 1; i <= right; i++)
                   if(v[i] < v[left])
                          swap(v, ++last,i);           swap(v, left, last);
           qsort(v , left, last - 1);
           qsort(v, last - 1, right);
}

Wow! That is an extremely tiny quicksort!

Have you tested it -- does it work? If so, my guess would be that a little redundancy was allowed for the sake of making it smaller.

but my question is how are the values in i & last swapped, when is seems that both i & last would have the same value..

Can anybody explain???

It is possible for a if statement to be false. Do you think that if statements always must be true? Doesn't work like that.

In the worst possible case, where v[i] is always less than v[left], the routine will march along always swapping nothing. As a side effect of the (no-op) swap last is incremented. We need that side effect so the swap is performed regardless of whether it's really swapping.

But suppose that the worst possible case does not arise. If the routine should ever encounter even a single case where v[i] is not less than v[left], last and i would move out of sync. This would last for the rest of the loop, once out of sync, they could never sync up again.

If this bums you out too much, put a test in the swap routine to inhibit the swap if you are not really swapping. But now you are performing a test for every swap. The superfluous test will slow you down if it rarely inhibits a swap. But if it winds up inhibiting most of them, it might be worth it. It's your call...how pessimistic are you?