1 /* 2 * qsort.c 3 * 4 * This is actually combsort. It's an O(n log n) algorithm with 5 * simplicity/small code size being its main virtue. 6 */ 7 8 #include <stddef.h> 9 #include <stdlib.h> 10 #include <string.h> 11 12 static inline size_t newgap(size_t gap) 13 { 14 gap = (gap * 10) / 13; 15 if (gap == 9 || gap == 10) 16 gap = 11; 17 18 if (gap < 1) 19 gap = 1; 20 return gap; 21 } 22 23 void qsort(void *base, size_t nmemb, size_t size, 24 int (*compar) (const void *, const void *)) 25 { 26 size_t gap = nmemb; 27 size_t i, j; 28 char *p1, *p2; 29 int swapped; 30 31 if (!nmemb) 32 return; 33 34 do { 35 gap = newgap(gap); 36 swapped = 0; 37 38 for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) { 39 j = i + gap; 40 if (compar(p1, p2 = (char *)base + j * size) > 0) { 41 memswap(p1, p2, size); 42 swapped = 1; 43 } 44 } 45 } while (gap > 1 || swapped); 46 } 47
