-

       


 

#include <limits.h>

#define MAXSTACK (sizeof(size_t) * CHAR_BIT)

 

static void exchange(void *a, void *b, size_t size) {

size_t i;

 

/******************

* exchange a,b *

******************/

 

for (i = sizeof(int); i <= size; i += sizeof(int)) {

int t = *((int *)a);



*(((int *)a)++) = *((int *)b);

*(((int *)b)++) = t;

}

for (i = i - sizeof(int) + 1; i <= size; i++) {

char t = *((char *)a);

*(((char *)a)++) = *((char *)b);

*(((char *)b)++) = t;

}

}

 

void qsort(void *base, size_t nmemb, size_t size,

int (*compar)(const void *, const void *)) {

void *lbStack[MAXSTACK], *ubStack[MAXSTACK];

int sp;

unsigned int offset;

 

lbStack[0] = (char *)base;

ubStack[0] = (char *)base + (nmemb-1)*size;

for (sp = 0; sp >= 0; sp--) {

char *lb, *ub, *m;

char *P, *i, *j;

 

lb = lbStack[sp];

ub = ubStack[sp];

 

while (lb < ub) {

 

/* select pivot and exchange with 1st element */

offset = (ub - lb) >> 1;

P = lb + offset - offset % size;

exchange (lb, P, size);

 

/* partition into two segments */

i = lb + size;

j = ub;

while (1) {

while (i < j && compar(lb, i) > 0) i += size;

while (j >= i && compar(j, lb) > 0) j -= size;

if (i >= j) break;

exchange (i, j, size);

j -= size;

i += size;

}

 

/* pivot belongs in A[j] */

exchange (lb, j, size);

m = j;

 

/* keep processing smallest segment, and stack largest */

if (m - lb <= ub - m) {

if (m + size < ub) {

lbStack[sp] = m + size;

ubStack[sp++] = ub;

}

ub = m - size;

} else {

if (m - size > lb) {

lbStack[sp] = lb;

ubStack[sp++] = m - size;

}

lb = m + size;

}

}

}

}