By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,339 Members | 1,973 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,339 IT Pros & Developers. It's quick & easy.

help in quicksort

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

Nov 12 '06 #1
Share this Question
Share on Google+
7 Replies


P: n/a
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
es*****@acm-dot-org.invalid
Nov 12 '06 #2

P: n/a
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/
Nov 12 '06 #3

P: n/a
In article <Nq******************************@comcast.com>,
Eric Sosman <es*****@acm-dot-org.invalidwrote:
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.
Nov 12 '06 #4

P: n/a
"zoro" <om********@nospam.yahoo.comwrote in message
news:f2******************************@localhost.ta lkaboutprogramming.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

Nov 12 '06 #5

P: n/a
On Nov 12, 4:04 pm, "Ivan Vecerina"
<_INVALID_use_webfo...@ivan.vecerina.comwrote:
"zoro" <omarzah...@nospam.yahoo.comwrote in messagenews:f2******************************@local host.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?
(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

Nov 13 '06 #6

P: n/a

Philip Guenther wrote:
On Nov 12, 4:04 pm, "Ivan Vecerina"
<_INVALID_use_webfo...@ivan.vecerina.comwrote:
"zoro" <omarzah...@nospam.yahoo.comwrote in messagenews:f2******************************@local host.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?
(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.programming was the most sensible place for this
question.
Philip Guenther
Nov 14 '06 #7

P: n/a
Philip Guenther wrote:
>
On Nov 12, 4:04 pm, "Ivan Vecerina"
<_INVALID_use_webfo...@ivan.vecerina.comwrote:
"zoro" <omarzah...@nospam.yahoo.com>
wrote in
messagenews:f28a7b425be86675af5f495cad5945e5@local host.
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
Nov 14 '06 #8

This discussion thread is closed

Replies have been disabled for this discussion.