1 /* 2 FUNCTION 3 <<qsort>>---sort an array 4 5 INDEX 6 qsort 7 8 ANSI_SYNOPSIS 9 #include <stdlib.h> 10 void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>, 11 int (*<[compar]>)(const void *, const void *) ); 12 13 TRAD_SYNOPSIS 14 #include <stdlib.h> 15 qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> ) 16 char *<[base]>; 17 size_t <[nmemb]>; 18 size_t <[size]>; 19 int (*<[compar]>)(); 20 21 DESCRIPTION 22 <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects. 23 <[size]> describes the size of each element of the array. 24 25 You must supply a pointer to a comparison function, using the argument 26 shown as <[compar]>. (This permits sorting objects of unknown 27 properties.) Define the comparison function to accept two arguments, 28 each a pointer to an element of the array starting at <[base]>. The 29 result of <<(*<[compar]>)>> must be negative if the first argument is 30 less than the second, zero if the two arguments match, and positive if 31 the first argument is greater than the second (where ``less than'' and 32 ``greater than'' refer to whatever arbitrary ordering is appropriate). 33 34 The array is sorted in place; that is, when <<qsort>> returns, the 35 array elements beginning at <[base]> have been reordered. 36 37 RETURNS 38 <<qsort>> does not return a result. 39 40 PORTABILITY 41 <<qsort>> is required by ANSI (without specifying the sorting algorithm). 42 */ 43 44 /*- 45 * Copyright (c) 1992, 1993 46 * The Regents of the University of California. All rights reserved. 47 * 48 * Redistribution and use in source and binary forms, with or without 49 * modification, are permitted provided that the following conditions 50 * are met: 51 * 1. Redistributions of source code must retain the above copyright 52 * notice, this list of conditions and the following disclaimer. 53 * 2. Redistributions in binary form must reproduce the above copyright 54 * notice, this list of conditions and the following disclaimer in the 55 * documentation and/or other materials provided with the distribution. 56 * 3. All advertising materials mentioning features or use of this software 57 * must display the following acknowledgement: 58 * This product includes software developed by the University of 59 * California, Berkeley and its contributors. 60 * 4. Neither the name of the University nor the names of its contributors 61 * may be used to endorse or promote products derived from this software 62 * without specific prior written permission. 63 * 64 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 65 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 66 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 67 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 68 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 69 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 70 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 71 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 72 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 73 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 74 * SUCH DAMAGE. 75 */ 76 77 #include <_ansi.h> 78 #include <stdlib.h> 79 80 #ifndef __GNUC__ 81 #define inline 82 #endif 83 84 static inline char *med3 _PARAMS((char *, char *, char *, int (*)())); 85 static inline void swapfunc _PARAMS((char *, char *, int, int)); 86 87 #define min(a, b) (a) < (b) ? a : b 88 89 /* 90 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 91 */ 92 #define swapcode(TYPE, parmi, parmj, n) { \ 93 long i = (n) / sizeof (TYPE); \ 94 register TYPE *pi = (TYPE *) (parmi); \ 95 register TYPE *pj = (TYPE *) (parmj); \ 96 do { \ 97 register TYPE t = *pi; \ 98 *pi++ = *pj; \ 99 *pj++ = t; \ 100 } while (--i > 0); \ 101 } 102 103 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 104 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; 105 106 static inline void 107 _DEFUN(swapfunc, (a, b, n, swaptype), 108 char *a _AND 109 char *b _AND 110 int n _AND 111 int swaptype) 112 { 113 if(swaptype <= 1) 114 swapcode(long, a, b, n) 115 else 116 swapcode(char, a, b, n) 117 } 118 119 #define swap(a, b) \ 120 if (swaptype == 0) { \ 121 long t = *(long *)(a); \ 122 *(long *)(a) = *(long *)(b); \ 123 *(long *)(b) = t; \ 124 } else \ 125 swapfunc(a, b, es, swaptype) 126 127 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) 128 129 static inline char * 130 _DEFUN(med3, (a, b, c, cmp), 131 char *a _AND 132 char *b _AND 133 char *c _AND 134 int (*cmp)()) 135 { 136 return cmp(a, b) < 0 ? 137 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) 138 :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); 139 } 140 141 void 142 _DEFUN(qsort, (a, n, es, cmp), 143 void *a _AND 144 size_t n _AND 145 size_t es _AND 146 int (*cmp)()) 147 { 148 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 149 int d, r, swaptype, swap_cnt; 150 151 loop: SWAPINIT(a, es); 152 swap_cnt = 0; 153 if (n < 7) { 154 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) 155 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 156 pl -= es) 157 swap(pl, pl - es); 158 return; 159 } 160 pm = (char *) a + (n / 2) * es; 161 if (n > 7) { 162 pl = a; 163 pn = (char *) a + (n - 1) * es; 164 if (n > 40) { 165 d = (n / 8) * es; 166 pl = med3(pl, pl + d, pl + 2 * d, cmp); 167 pm = med3(pm - d, pm, pm + d, cmp); 168 pn = med3(pn - 2 * d, pn - d, pn, cmp); 169 } 170 pm = med3(pl, pm, pn, cmp); 171 } 172 swap(a, pm); 173 pa = pb = (char *) a + es; 174 175 pc = pd = (char *) a + (n - 1) * es; 176 for (;;) { 177 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 178 if (r == 0) { 179 swap_cnt = 1; 180 swap(pa, pb); 181 pa += es; 182 } 183 pb += es; 184 } 185 while (pb <= pc && (r = cmp(pc, a)) >= 0) { 186 if (r == 0) { 187 swap_cnt = 1; 188 swap(pc, pd); 189 pd -= es; 190 } 191 pc -= es; 192 } 193 if (pb > pc) 194 break; 195 swap(pb, pc); 196 swap_cnt = 1; 197 pb += es; 198 pc -= es; 199 } 200 if (swap_cnt == 0) { /* Switch to insertion sort */ 201 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) 202 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 203 pl -= es) 204 swap(pl, pl - es); 205 return; 206 } 207 208 pn = (char *) a + n * es; 209 r = min(pa - (char *)a, pb - pa); 210 vecswap(a, pb - r, r); 211 r = min(pd - pc, pn - pd - es); 212 vecswap(pb, pn - r, r); 213 if ((r = pb - pa) > es) 214 qsort(a, r / es, es, cmp); 215 if ((r = pd - pc) > es) { 216 /* Iterate rather than recurse to save stack space */ 217 a = pn - r; 218 n = r / es; 219 goto loop; 220 } 221 /* qsort(pn - r, r / es, es, cmp);*/ 222 } 223