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