qsort.c (1321B)
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 /* 27 * This function recurses as much as log2(n) because 28 * it always recurses in the smaller part of the 29 * array. 30 */ 31 static void 32 xqsort(char *a, size_t n, struct qsort *qs) 33 { 34 size_t nj, ni, es = qs->es; 35 char *pi, *pj, *pn; 36 37 if (n <= 1) 38 return; 39 40 pi = a; 41 pn = pj = a + n*es; 42 43 swap(a, a + n/2 * es, es); 44 for (;;) { 45 do { 46 pi += es; 47 } while (pi < pn && qs->cmp(pi, a) < 0); 48 49 do { 50 pj -= es; 51 } while (pj > a && qs->cmp(pj, a) > 0); 52 53 if (pj < pi) 54 break; 55 swap(pi, pj, es); 56 } 57 swap(a, pj, es); 58 59 pi = a; 60 ni = (pj - a) / es; 61 pj += es; 62 nj = n-nj-1; 63 64 if (ni < nj) { 65 xqsort(pi, ni, qs); 66 xqsort(pj, nj, qs); 67 } else { 68 xqsort(pj, nj, qs); 69 xqsort(pi, ni, qs); 70 } 71 } 72 73 void 74 qsort(void *base, size_t nmemb, size_t size, 75 int (*f)(const void *, const void *)) 76 { 77 struct qsort qs; 78 79 qs.cmp = f; 80 qs.es = size; 81 xqsort(base, nmemb, &qs); 82 }