help in quicksort

Discussion in 'C Programming' started by zoro, Nov 12, 2006.

  1. zoro

    zoro Guest

    how many recursive calls will quicksort make in the worst case for a file
    of N items?
    thank you
    zoro, Nov 12, 2006
    #1
    1. Advertising

  2. zoro

    Eric Sosman Guest

    zoro wrote:
    > how many recursive calls will quicksort make in the worst case for a file
    > of N items?


    Wrong newsgroup: there's no "quicksort" in the C language.
    Try a different newsgroup, like alt.do.your.own.stupid.homework
    or or alt.careers.in.sewer.maintenance.

    --
    Eric Sosman
    lid
    Eric Sosman, Nov 12, 2006
    #2
    1. Advertising

  3. zoro

    Martijn Guest

    Eric Sosman wrote:
    > zoro wrote:
    >> how many recursive calls will quicksort make in the worst case for a
    >> file of N items?

    >
    > Wrong newsgroup: there's no "quicksort" in the C language.
    > Try a different newsgroup, like alt.do.your.own.stupid.homework
    > or or alt.careers.in.sewer.maintenance.


    Hmm, you might have misinterpreted the question, there is nothing on job
    seeking or DIY, let alone specific to waste drainage and its upkeep.

    Anyway, to answer the OP (or at least, partly): If you do the worst case
    scenario on a piece of paper for a set of, say, five elements, you should be
    easily able to figure this one out.

    Or ask your question elsewhere. GIYF: quicksort recurse depth

    --
    Martijn
    http://www.sereneconcepts.nl
    http://blogger.xs4all.nl/mihaak/
    Martijn, Nov 12, 2006
    #3
  4. In article <>,
    Eric Sosman <> wrote:

    > Wrong newsgroup: there's no "quicksort" in the C language.


    An understandable mistake, given the unfortunate decision to call the
    sort function "qsort()".

    -- Richard
    --
    "Consideration shall be given to the need for as many as 32 characters
    in some alphabets" - X3.4, 1963.
    Richard Tobin, Nov 12, 2006
    #4
  5. "zoro" <> wrote in message
    news:...
    : how many recursive calls will quicksort make in the worst case
    : for a file of N items?
    This depends on the implementation of the algorithm.
    A naive implementation could have a worst case of N, but
    a decent implementation (which qsort() should be in your
    C library) will have a worst case of lg(N) recursions.
    [ it is common for industrial strength implementations
    to recurse on the smaller partition and iterate on
    the larger one ]


    hth -Ivan
    --
    http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
    Ivan Vecerina, Nov 12, 2006
    #5
  6. On Nov 12, 4:04 pm, "Ivan Vecerina"
    <> wrote:
    > "zoro" <> wrote in messagenews:...
    > : how many recursive calls will quicksort make in the worst case
    > : for a file of N items?
    > This depends on the implementation of the algorithm.
    > A naive implementation could have a worst case of N, but
    > a decent implementation (which qsort() should be in your
    > C library) will have a worst case of lg(N) recursions.


    While I see how you can limit the worst case _depth_ of recursion to
    O(log N), the worst case _count_ of recursive calls is still O(N), no?
    (The data arrangements that hit the worst cases for those two are
    different, of course.)

    I seem to recall a USENIX paper from 2000 or 2001 co-authored by Doug
    McIlroy, in which the authors described a torture test for quicksort
    which dynamically created a worst-case data arrangement for whatever
    quicksort implementation it was given.


    Philip Guenther
    Philip Guenther, Nov 13, 2006
    #6
  7. zoro

    Guest

    Philip Guenther wrote:
    > On Nov 12, 4:04 pm, "Ivan Vecerina"
    > <> wrote:
    > > "zoro" <> wrote in messagenews:...
    > > : how many recursive calls will quicksort make in the worst case
    > > : for a file of N items?
    > > This depends on the implementation of the algorithm.
    > > A naive implementation could have a worst case of N, but
    > > a decent implementation (which qsort() should be in your
    > > C library) will have a worst case of lg(N) recursions.

    >
    > While I see how you can limit the worst case _depth_ of recursion to
    > O(log N), the worst case _count_ of recursive calls is still O(N), no?
    > (The data arrangements that hit the worst cases for those two are
    > different, of course.)
    >
    > I seem to recall a USENIX paper from 2000 or 2001 co-authored by Doug
    > McIlroy, in which the authors described a torture test for quicksort
    > which dynamically created a worst-case data arrangement for whatever
    > quicksort implementation it was given.


    Bentley was the other author:
    http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol23/issue11/spe862jb.pdf

    There is an adversary set for any given input vector and partitioning
    scheme.

    The usual solution is to switch to heapsort when we have recursed
    log(n) times and the sort has not finished. (Introspective sort does
    this).

    Probably, news:comp.programming was the most sensible place for this
    question.

    > Philip Guenther
    , Nov 14, 2006
    #7
  8. zoro

    pete Guest

    Philip Guenther wrote:
    >
    > On Nov 12, 4:04 pm, "Ivan Vecerina"
    > <> wrote:
    > > "zoro" <>
    > > wrote in
    > >messagenews:f28a7b425be86675af5f495cad5945e5@localhost.
    > >talkaboutprogramming.com...
    > > : how many recursive calls will quicksort make in the worst case
    > > : for a file of N items?
    > > This depends on the implementation of the algorithm.
    > > A naive implementation could have a worst case of N, but
    > > a decent implementation (which qsort() should be in your
    > > C library) will have a worst case of lg(N) recursions.

    >
    > While I see how you can limit the worst case _depth_ of recursion to
    > O(log N), the worst case _count_ of recursive calls is still O(N), no?


    You are correct about that
    for the kinds recursion schemes that Ivan Vecerina suggested
    as in q0sort and q1sort,
    but "This depends on the implementation of the algorithm."
    is still true, since the quicksort algorithm
    can also be implemented nonrecursively, as in q2sort.

    #include <stddef.h>
    #include <limits.h>

    #define BYTE_SWAP(A, B) \
    { \
    p1 = (A); \
    p2 = (B); \
    end = p2 + size; \
    do { \
    swap = *p1; \
    *p1++ = *p2; \
    *p2++ = swap; \
    } while (p2 != end); \
    }

    void q0sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void*, const void*));
    void q1sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void*, const void*));
    void q2sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *));

    void q0sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void*, const void*))
    {
    unsigned char *left;
    unsigned char *p1, *p2, *end, swap;
    size_t nmemb_right, middle, last, right;

    if (nmemb-- > 1) {
    left = base;
    right = last = nmemb * size;
    middle = size;
    while (compar(left, left + middle) > 0 && middle != right) {
    middle += size;
    }
    while (compar(left + last, left) > 0) {
    last -= size;
    }
    while (last > middle) {
    BYTE_SWAP(left + middle, left + last);
    do {
    middle += size;
    } while (compar(left, left + middle) > 0);
    do {
    last -= size;
    } while (compar(left + last, left) > 0);
    }
    BYTE_SWAP(left, left + last);
    nmemb = last / size;
    nmemb_right = (right - last) / size;
    q0sort(last + size + left, nmemb_right, size, compar);
    q0sort(base, nmemb, size, compar);
    }
    }

    void q1sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void*, const void*))
    {
    unsigned char *left;
    size_t nmemb_right, middle, last, right;
    unsigned char *p1, *p2, *end, swap;

    left = base;
    while (nmemb-- > 1) {
    right = last = nmemb * size;
    middle = size;
    while (compar(left, left + middle) > 0 && middle != right) {
    middle += size;
    }
    while (compar(left + last, left) > 0) {
    last -= size;
    }
    while (last > middle) {
    BYTE_SWAP(left + middle, left + last);
    do {
    middle += size;
    } while (compar(left, left + middle) > 0);
    do {
    last -= size;
    } while (compar(left + last, left) > 0);
    }
    BYTE_SWAP(left, left + last);
    nmemb = last / size;
    nmemb_right = (right - last) / size;
    if (nmemb_right > nmemb) {
    q1sort(left, nmemb, size, compar);
    left += last + size;
    nmemb = nmemb_right;
    } else {
    q1sort(left + last + size, nmemb_right, size, compar);
    }
    }
    }

    void q2sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *))
    {
    unsigned char *left;
    size_t middle, last, right;
    struct {
    size_t bytes;
    void *base;
    } stack[CHAR_BIT * sizeof nmemb], *stack_ptr;
    unsigned char *p1, *p2, *end, swap;

    stack -> bytes = nmemb * size;
    stack -> base = base;
    stack_ptr = stack + 1;
    do {
    --stack_ptr;
    if (stack_ptr -> bytes > size) {
    left = stack_ptr -> base;
    right = last = stack_ptr -> bytes - size;
    middle = size;
    while (compar(left, left + middle) > 0
    && middle != right)
    {
    middle += size;
    }
    while (compar(left + last, left) > 0) {
    last -= size;
    }
    while (last > middle) {
    BYTE_SWAP(left + middle, left + last);
    do {
    middle += size;
    } while (compar(left, left + middle) > 0);
    do {
    last -= size;
    } while (compar(left + last, left) > 0);
    }
    BYTE_SWAP(left, left + last);
    if (right - last > last) {
    stack_ptr -> base = left + last + size;
    stack_ptr++ -> bytes = right - last;
    stack_ptr -> base = left;
    stack_ptr++ -> bytes = last;
    } else {
    stack_ptr++ -> bytes = last;
    stack_ptr -> base = left + last + size;
    stack_ptr++ -> bytes = right - last;
    }
    }
    } while (stack_ptr != stack);
    }

    --
    pete
    pete, Nov 14, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sarah
    Replies:
    2
    Views:
    3,239
    Roedy Green
    Oct 23, 2003
  2. hiwa
    Replies:
    4
    Views:
    627
    Esmond Pitt
    Mar 29, 2005
  3. Exekute

    c++ and quicksort

    Exekute, Sep 27, 2003, in forum: C++
    Replies:
    6
    Views:
    9,014
    Jerry Coffin
    Sep 28, 2003
  4. David Sachs

    Re: c++ and quicksort

    David Sachs, Sep 28, 2003, in forum: C++
    Replies:
    1
    Views:
    467
    Gianni Mariani
    Sep 28, 2003
  5. Alex Vinokur
    Replies:
    0
    Views:
    966
    Alex Vinokur
    Aug 30, 2004
Loading...

Share This Page