quicksort special case - seems to be a faulty algorithm from K&R

Question

I have a problem understanding quicksort algorithm (the simplified version without pointers) from K&R. There is already a thorough explanation provided by Dave Gamble here explanation. However I noticed that by starting with a slightly changed string we can obtain no swaps during many loops of the for loop. Firstly the code:

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);
}

Walkthrough in my opinion:

we start with CADBE; left=0; right=4; D is the pivot so according to algorithm we swap D with C obtaining DACBE

last = left =0

i = 1 if ( v1 < v[0] ) it is true so we swap v1 (because last is incremented before operation) with v1 so nothing changes, last = 1, still having DACBE;

now i = 2 if ( v[2] < v[0] ) -> true so we swap v[2] with v[2] nothing changed again; last = 2

now i = 3 if ( v[3] < v[0] ) -> true so we swap v[3] with v[3] nothing changed AGAIN (!), last = 3

So apparently something is wrong, algorithm does nothing. Your opinions appreciated very much. I must be wrong, authors are better than me ;D Thanks in advance!

You have not finished the walk through. What happens after the last swap, just before the first recursive call to qsort? — n. m. could be an AI, Aug 13 '12 at 17:28

Nemo · Accepted Answer · 2012-08-13T19:34:09.430

3

The loop goes from left + 1 up to and including right. When i=4, the test fails and last does not get incremented.

Then the recursive calls sort BACDE with left=0,right=2 and left=4,right=4. (Which is correct when D is the pivot.)

edited Aug 13 '12 at 19:34

answered Aug 13 '12 at 17:29

Nemo

70,042
10
116
153

Thanks. But when it comes to recursive calls don't we start with BACDE with left=0 and right=2 (last-1) ? – Peter Cerba Aug 13 '12 at 19:23

AnT stands with Russia · Answer 2 · 2012-08-13T17:34:32.900

Well, it just so happened that your input sub-array ACBE is already partitioned by D (ACB is smaller than D and E is bigger than D), so it is not surprising the partitioning cycle does not physically swap any values.

In reality, it is not correct to say that it "does nothing". It does not reorder anything in the cycle, since your input data need no extra reordering. But it still does one thing: it finds the value of last that says where smaller elements end and bigger elements begin, i.e. it separates ACBE into ACB and E parts. The cycle ends with last == 3, which is the partitioning point for further recursive steps.

quicksort special case - seems to be a faulty algorithm from K&R

2 Answers2

Linked