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]

Re: help in quicksort

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.homewor k
or or alt.careers.in. sewer.maintenan ce.

--
Eric Sosman
esosman@acm-dot-org.invalid

[Martijn]

Re: help in quicksort

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.homewor k
or or alt.careers.in. sewer.maintenan ce.

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/

[Richard Tobin]

Re: help in quicksort

In article <Nqqdncmy7rJ44c rYnZ2dnUVZ_uSdn Z2d@comcast.com >,
Eric Sosman <esosman@acm-dot-org.invalidwrot e:

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

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

-- Richard
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Ivan Vecerina]

Re: help in quicksort

"zoro" <omarzahdan@nos pam.yahoo.comwr ote in message
news:f28a7b425b e86675af5f495ca d5945e5@localho st.talkaboutpro gramming.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.
[ 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

[Philip Guenther]

Re: help in quicksort

On Nov 12, 4:04 pm, "Ivan Vecerina"
<_INVALID_use_w ebfo...@ivan.ve cerina.comwrote :

"zoro" <omarzah...@nos pam.yahoo.comwr ote in messagenews:f28 a7b425be86675af 5f495cad5945e5@ localhost.talka boutprogramming .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?
(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@connx.com]

Re: help in quicksort


Philip Guenther wrote:

On Nov 12, 4:04 pm, "Ivan Vecerina"
<_INVALID_use_w ebfo...@ivan.ve cerina.comwrote :

"zoro" <omarzah...@nos pam.yahoo.comwr ote in messagenews:f28 a7b425be86675af 5f495cad5945e5@ localhost.talka boutprogramming .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?
(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/p...1/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.progr amming was the most sensible place for this
question.

Philip Guenther

[pete]

Re: help in quicksort

Philip Guenther wrote:

>
On Nov 12, 4:04 pm, "Ivan Vecerina"
<_INVALID_use_w ebfo...@ivan.ve cerina.comwrote :

"zoro" <omarzah...@nos pam.yahoo.com>
wrote in
messagenews:f28 a7b425be86675af 5f495cad5945e5@ localhost.
talkaboutprogra mming.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