qsort.c (1097B)
1 #include <stdlib.h> 2 #include <string.h> 3 #undef qsort 4 5 /* 6 * This implementation of qsort is based in the paper 7 * "Engineering a Sort Function", by Jon L.Bentley and M. Douglas McIlroy. 8 * A lot of different optimizations were removed to make the code simpler. 9 */ 10 11 struct qsort { 12 size_t es; 13 int (*cmp)(const void *, const void *); 14 }; 15 16 static void 17 swap(char *i, char *j, size_t n) 18 { 19 do { 20 char c = *i; 21 *i++ = *j; 22 *j++ = c; 23 } while (--n > 0); 24 } 25 26 static void 27 xqsort(char *a, size_t n, struct qsort *qs) 28 { 29 size_t j, es = qs->es; 30 char *pi, *pj, *pn; 31 32 if (n <= 1) 33 return; 34 35 pi = a; 36 pn = pj = a + n*es; 37 38 swap(a, a + n/2 * es, es); 39 for (;;) { 40 do { 41 pi += es; 42 } while (pi < pn && qs->cmp(pi, a) < 0); 43 44 do { 45 pj -= es; 46 } while (pj > a && qs->cmp(pj, a) > 0); 47 48 if (pj < pi) 49 break; 50 swap(pi, pj, es); 51 } 52 swap(a, pj, es); 53 54 j = (pj - a) / es; 55 xqsort(a, j, qs); 56 xqsort(a + (j+1)*es, n-j-1, qs); 57 } 58 59 void 60 qsort(void *base, size_t nmemb, size_t size, 61 int (*f)(const void *, const void *)) 62 { 63 struct qsort qs; 64 65 qs.cmp = f; 66 qs.es = size; 67 xqsort(base, nmemb, &qs); 68 }