[1] | 1 | #include <stdlib.h> |
---|

| 2 | |
---|

| 3 | static void exch(char* base,size_t size,size_t a,size_t b) { |
---|

| 4 | char* x=base+a*size; |
---|

| 5 | char* y=base+b*size; |
---|

| 6 | while (size) { |
---|

| 7 | char z=*x; |
---|

| 8 | *x=*y; |
---|

| 9 | *y=z; |
---|

| 10 | --size; ++x; ++y; |
---|

| 11 | } |
---|

| 12 | } |
---|

| 13 | |
---|

| 14 | /* Quicksort with 3-way partitioning, ala Sedgewick */ |
---|

| 15 | /* Blame him for the scary variable names */ |
---|

| 16 | /* http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf */ |
---|

| 17 | static void quicksort(char* base,size_t size,ssize_t l,ssize_t r, |
---|

| 18 | int (*compar)(const void*,const void*)) { |
---|

| 19 | ssize_t i=l-1, j=r, p=l-1, q=r, k; |
---|

| 20 | char* v=base+r*size; |
---|

| 21 | if (r<=l) return; |
---|

| 22 | for (;;) { |
---|

| 23 | while (++i != r && compar(base+i*size,v)<0) ; |
---|

| 24 | while (compar(v,base+(--j)*size)<0) if (j == l) break; |
---|

| 25 | if (i >= j) break; |
---|

| 26 | exch(base,size,i,j); |
---|

| 27 | if (compar(base+i*size,v)==0) exch(base,size,++p,i); |
---|

| 28 | if (compar(v,base+j*size)==0) exch(base,size,j,--q); |
---|

| 29 | } |
---|

| 30 | exch(base,size,i,r); j = i-1; ++i; |
---|

| 31 | for (k=l; k<p; k++, j--) exch(base,size,k,j); |
---|

| 32 | for (k=r-1; k>q; k--, i++) exch(base,size,i,k); |
---|

| 33 | quicksort(base,size,l,j,compar); |
---|

| 34 | quicksort(base,size,i,r,compar); |
---|

| 35 | } |
---|

| 36 | |
---|

| 37 | void qsort(void* base,size_t nmemb,size_t size,int (*compar)(const void*,const void*)) { |
---|

| 38 | /* check for integer overflows */ |
---|

| 39 | if (nmemb >= (((size_t)-1)>>1) || |
---|

| 40 | size >= (((size_t)-1)>>1)) return; |
---|

| 41 | #if 0 |
---|

| 42 | if (sizeof(size_t) < sizeof(unsigned long long)) { |
---|

| 43 | if ((unsigned long long)size * nmemb > (size_t)-1) return; |
---|

| 44 | } else { |
---|

| 45 | if (size*nmemb/nmemb != size) return; |
---|

| 46 | } |
---|

| 47 | #endif |
---|

| 48 | if (nmemb>1) |
---|

| 49 | quicksort(base,size,0,nmemb-1,compar); |
---|

| 50 | } |
---|