qsort -> please explain-it

Code:

---

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

---

if we have these inputs e.g. {11, 3, 9, 7, 4)

Just a bit... so that I can proceed!

Quote:

---

Originally Posted by c_lady

if we have these inputs e.g. {11, 3, 9, 7, 4)

---

First you choose a pivot value. Let's take an average of the low and high, which would be 7. Everything less than or equal to the pivot goes to the "left" (7, 4, 3), everything else "right" (11, 9), and quicksort is called recursively.

There are only two elements remaining on the right, so these are compared and returned in order (9, 11) to the first level of recursion.

There are more than 2 on the left, so we split again. The pivot is now 5, so 7 goes right and (4, 3) goes left. Now there are only two elements left -- compare and return (3, 4). 7 is returned by itself and the two returned lists are combined left->right, so the second level of recursion returns (3, 4, 7) from the left.

Back to the first level of recursion the returned lists are combined, (3, 4, 7, 9, 11).

Except the pivot in the OP's code is chosen using the average of subscripts and not values, because the function always wants to use the middle element.

Actually, that whole explanation is wonky. "Fewer than two" means the algorithm will run when there are two elements to be sorted. When you use qsort, the pivot is the only element that is actually sorted by the algorithm. It recursively sorts subarrays on both sides of the pivot, until the array is pared down to one element. Then you have your sorted array.

Ah, I didn't pay that much attention to that code since "swap" is not defined in the example.

How you pick the pivot is very important, quick sort totally sucks with a bad pivot value because it leads to lopsided lists and excessive recursion.

This is why I still insist mergesort is a better general purpose sort, because the depth of the recursion is definite.

Code:

---

/* 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;
}

---

@MK27, please try now to make me the correct explanation based on the above code! and above inputs such as: {11, 3, 9, 7, 4)

I am really looking forward to your answers!

why NoOne is not a bit helpful? ...

Quote:

---

Originally Posted by c_lady

why NoOne is not a bit helpful? ...

---

I'm not convinced that the code you posted even works -- do you know that it does? In any case, it is not the best example to understand quicksort with because the mechanism is not clear.

Unfortunately the only code example I have at hand is very longwinded, I'll spare you that.

If you need to write your own quicksort, I would look around for some other sources of code and explanation beyond that one example. If you write some code and it does not work properly, you can always post that and ask why -- I'm sure lots of people will help with that.

But this code is from K&R - C Programming Language! Is possible that code to not work :(

Quote:

---

Originally Posted by c_lady

But this code is from K&R - C Programming Language! Is possible that code to not work :(

---

Presumably it works then, so I don't mind trying to explain it.

Presumably left and right are the starting indexes in array "v", so you would have to set those initially yourself. Let's make left 0 and right 3 for array (11, 3, 9, 7, 4).

Code:

---

swap(v, left, (left + right)/2); /* move partition elem */

---

Now the array will look like (3, 11, 9, 7, 4).

Code:

---

last = left; /* to v[0] */
for (i = left + 1; i <= right; i++) /* partition */
if (v[i] < v[left])  // my note: remember this
swap(v, ++last, i);

---

So starting at 1 and ending at 2:
1) compare v[1] v[0], v[1] is not < v[0].
2) compare v[2] v[0], v[2] is not < v[0].

Code:

---

swap(v, left, last); /* restore partition elem */

---

This makes no sense since last == left. No-op, continue.

Code:

---

qsort(v, left, last-1);
qsort(v, last+1, right);

---

For the next level of recursion, the left hand side (notice, quicksort is a forking recursion) parameters will be 0, -1.

This is a big problem. That code does NOT work. The problem is that last was never incremented because this:

Code:

---

if (v[i] < v[left])

---

was never true.

You won't learn quicksort from that. If you copy pasted this wrong to start with, do not expect me to try explaining it again -- sorry.

[edit] it just occurred to me that maybe right should be the last element...heh-heh...but I'm still not going thru it again. You can try next ;) hopefully you have the rest of the instructions.

Partitioning and pivot selection is all there is to quick sort so by all means watch it execute. That is what you are asking us to show.

The wysiwyg function will dump the array as-is and the current pivot when you first select the pivot, whenever there is a swap, and when the partition finishes. That way you can see your partitioning. Debugging would be able to show you this as well.

Code:

---

#include <stdio.h>

void wysiwyg(int v[], int left, int right, int pivot);

void wysiwyg(int v[], int left, int right, int pivot) {
    int i;
    fputs("( ", stdout);
    for (i = left; i < (right + 1); i++) {
        printf("%d, ", v[i]);
    }
    printf(") pivot=%d... \n", pivot);
    fflush(stdout);
}

/* 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); a misplaced prototype? */
    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] */
    wysiwyg(v, left, right, last);
    for (i = left + 1; i <= right; i++) /* partition */
    if (v[i] < v[left]) {
      swap(v, ++last, i);
      wysiwyg(v, left, right, last);
    }
    swap(v, left, last); /* restore partition elem */
    wysiwyg(v, left, right, last);
    qsort(v, left, last - 1);
    qsort(v, last + 1, right);
}

---

Use comments and you have a "quiet" quick sort again.

Quote:

---

Originally Posted by MK27

How you pick the pivot is very important, quick sort totally sucks with a bad pivot value because it leads to lopsided lists and excessive recursion.

This is why I still insist mergesort is a better general purpose sort, because the depth of the recursion is definite.

---

The depth of the recursion is limited to at most log(n) if you only recurse on the smaller portion.
That means that in code where I do this, it has less recursion than merge sort! :cool:
I certainly agree that quicksort's rather varied running time is annoying though, but that's where IntroSort comes in handy.

@MK27 I had the same conclusion! But simply I dont believe at myself ... but how come this kind of book may have mistakes :(

Quote:

---

Originally Posted by c_lady

@MK27 I had the same conclusion! But simply I dont believe at myself ... but how come this kind of book may have mistakes :(

---

Hey, I just posted a note to that above (check) -- maybe "right" should be the last element, so you start with 0, 4 for params? That would make more sense and it might work.

But I don't have the book, so...also, have you tried compiling this and testing it?

I think I know the problem. From my code contribution:

Code:

---

    if (v[i] < v[left]) {
      swap(v, ++last, i);
      wysiwyg(v, left, right, last);
    }

---

I did not make any changes to the algorithm beyond inserting new function calls and some prettifying.

The idea of the partition is to swap the last you picked with the first element, and then walk the array swapping v[last] with v[i] when v[i] is less than the left element. After each swap the 'last' is supposed to move. When the partition is done, the pivot is sorted (so you swap the first element back to where 'last' indicates); this is where you split subarrays.

It's a common implementation, but it was botched somewhere. I can't blame the books author. Every errata I can find mentions a different qsort they wrote (different from the standard, but with function pointers to compare things, which means its different from what is here).

I don't like that version of Quicksort. I like the versions where the pivot is left in place, and the left and right run down with their paired while loops, each finding an out of position value, and then they swap.

Seems simple and intuitive:

Code:

---

pivot = a[(left + right)/2];
while(a[i] < pivot) ++i;
while(a[j] > pivot) --j;
//etc.

---

I don't have that code on the system I'm on, but you can find it posted here, with a search.