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
