Thread: qsort -> please explain-it

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    94

    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!

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by c_lady View Post
    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).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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.
    Last edited by whiteflags; 05-11-2010 at 08:36 AM.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    94
    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!

  6. #6
    Registered User
    Join Date
    Mar 2010
    Posts
    94
    why NoOne is not a bit helpful? ...

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by c_lady View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Registered User
    Join Date
    Mar 2010
    Posts
    94
    But this code is from K&R - C Programming Language! Is possible that code to not work

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by c_lady View Post
    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.
    Last edited by MK27; 05-11-2010 at 01:22 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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.
    Last edited by whiteflags; 05-11-2010 at 12:52 PM.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by MK27 View Post
    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!
    I certainly agree that quicksort's rather varied running time is annoying though, but that's where IntroSort comes in handy.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Mar 2010
    Posts
    94
    @MK27 I had the same conclusion! But simply I dont believe at myself ... but how come this kind of book may have mistakes

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by c_lady View Post
    @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?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #14
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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).

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. small -> big -> bigger -> bigger than bigger -> ?
    By happyclown in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 03-11-2009, 12:12 PM
  2. An interesting problem of qsort()
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 03-05-2008, 12:09 PM
  3. Dev-C++ -> Tools - > Editor -> Syntax
    By Yuri2 in forum C++ Programming
    Replies: 19
    Last Post: 07-03-2006, 07:48 AM
  4. > > > Urgent Help < < <
    By CodeCypher in forum C Programming
    Replies: 2
    Last Post: 01-31-2006, 02:06 PM
  5. C++ link error with qsort
    By bvnorth in forum C++ Programming
    Replies: 7
    Last Post: 10-24-2003, 02:22 AM