help in quicksort

[zoro]

how many recursive calls will quicksort make in the worst case for a file
of N items?
thank you

 

[Eric Sosman]

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.

 

[Martijn]

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

 

[Richard Tobin]

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

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

-- Richard

 

[Ivan Vecerina]

: 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

 

[Philip Guenther]

: 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

 

[dcorbit]

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, was the most sensible place for this
question.

 

[pete]

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