1 /* 2 * qsort -- simple quicksort 3 */ 4 5 typedef 6 struct 7 { 8 int (*cmp)(void*, void*); 9 void (*swap)(char*, char*, long); 10 long es; 11 } Sort; 12 13 static void 14 swapb(char *i, char *j, long es) 15 { 16 char c; 17 18 do { 19 c = *i; 20 *i++ = *j; 21 *j++ = c; 22 es--; 23 } while(es != 0); 24 25 } 26 27 static void 28 swapi(char *ii, char *ij, long es) 29 { 30 long *i, *j, c; 31 32 i = (long*)ii; 33 j = (long*)ij; 34 do { 35 c = *i; 36 *i++ = *j; 37 *j++ = c; 38 es -= sizeof(long); 39 } while(es != 0); 40 } 41 42 static char* 43 pivot(char *a, long n, Sort *p) 44 { 45 long j; 46 char *pi, *pj, *pk; 47 48 j = n/6 * p->es; 49 pi = a + j; /* 1/6 */ 50 j += j; 51 pj = pi + j; /* 1/2 */ 52 pk = pj + j; /* 5/6 */ 53 if(p->cmp(pi, pj) < 0) { 54 if(p->cmp(pi, pk) < 0) { 55 if(p->cmp(pj, pk) < 0) 56 return pj; 57 return pk; 58 } 59 return pi; 60 } 61 if(p->cmp(pj, pk) < 0) { 62 if(p->cmp(pi, pk) < 0) 63 return pi; 64 return pk; 65 } 66 return pj; 67 } 68 69 static void 70 qsorts(char *a, long n, Sort *p) 71 { 72 long j, es; 73 char *pi, *pj, *pn; 74 75 es = p->es; 76 while(n > 1) { 77 if(n > 10) { 78 pi = pivot(a, n, p); 79 } else 80 pi = a + (n>>1)*es; 81 82 p->swap(a, pi, es); 83 pi = a; 84 pn = a + n*es; 85 pj = pn; 86 for(;;) { 87 do 88 pi += es; 89 while(pi < pn && p->cmp(pi, a) < 0); 90 do 91 pj -= es; 92 while(pj > a && p->cmp(pj, a) > 0); 93 if(pj < pi) 94 break; 95 p->swap(pi, pj, es); 96 } 97 p->swap(a, pj, es); 98 j = (pj - a) / es; 99 100 n = n-j-1; 101 if(j >= n) { 102 qsorts(a, j, p); 103 a += (j+1)*es; 104 } else { 105 qsorts(a + (j+1)*es, n, p); 106 n = j; 107 } 108 } 109 } 110 111 void 112 qsort(void *va, long n, long es, int (*cmp)(void*, void*)) 113 { 114 Sort s; 115 116 s.cmp = cmp; 117 s.es = es; 118 s.swap = swapi; 119 if(((long)va | es) % sizeof(long)) 120 s.swap = swapb; 121 qsorts((char*)va, n, &s); 122 } 123