1 /******************************************************************/
2 /* qsort.c -- Non-Recursive ANSI Quicksort function */
3 /* */
4 /* Public domain by Raymond Gardner, Englewood CO February 1991 */
5 /* */
6 /* Usage: */
7 /* qsort(base, nbr_elements, width_bytes, compare_function); */
8 /* void *base; */
9 /* size_t nbr_elements, width_bytes; */
10 /* int (*compare_function)(const void *, const void *); */
11 /* */
12 /* Sorts an array starting at base, of length nbr_elements, each */
13 /* element of size width_bytes, ordered via compare_function, */
14 /* which is called as (*compare_function)(ptr_to_element1, */
15 /* ptr_to_element2) and returns < 0 if element1 < element2, */
16 /* 0 if element1 = element2, > 0 if element1 > element2. */
17 /* Most refinements are due to R. Sedgewick. See "Implementing */
18 /* Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum, */
19 /* Comm. ACM, June 1979. */
20 /******************************************************************/
21
22 /* John E. Davis: modifed to use my coding style and made gcc warning
23 * clean. Also, the name changed to reflect the fact that the function
24 * carries state data.
25 */
26
27 #include <stddef.h> /* for size_t definition */
28
29 /* prototypes */
30 extern void _SLqsort (void *, size_t, size_t,
31 int (*)(void *, void *, void *), void *);
32
33 static void swap_chars(char *, char *, size_t);
34
35 /*
36 * Compile with -DSWAP_INTS if your machine can access an int at an
37 * arbitrary location with reasonable efficiency. Some machines
38 * cannot access an int at an odd address at all, so be careful.
39 */
40
41 #ifdef SWAP_INTS
42 static void swap_ints(char *, char *, size_t);
43 # define SWAP(a, b) (swap_func((char *)(a), (char *)(b), width))
44 #else
45 # define SWAP(a, b) (swap_chars((char *)(a), (char *)(b), size))
46 #endif
47
48 #define COMP(a, b, c) ((*comp)((void *)(a), (void *)(b), (c)))
49
50 #define T 7
51 /* subfiles of T or fewer elements will be sorted by a simple insertion sort.
52 * Note! T must be at least 3
53 */
54
_SLqsort(void * basep,size_t nelems,size_t size,int (* comp)(void *,void *,void *),void * cd)55 void _SLqsort(void *basep, size_t nelems, size_t size,
56 int (*comp)(void *, void *, void *), void *cd)
57 {
58 char *stack[40], **sp; /* stack and stack pointer */
59 char *i, *j, *limit; /* scan and limit pointers */
60 size_t thresh; /* size of T elements in bytes */
61 char *base; /* base pointer as char * */
62
63 #ifdef SWAP_INTS
64 size_t width; /* width of array element */
65 void (*swap_func)(char *, char *, size_t); /* swap func pointer*/
66
67 width = size; /* save size for swap routine */
68 swap_func = swap_chars; /* choose swap function */
69 if ( size % sizeof(int) == 0 )
70 {
71 /* size is multiple of ints */
72 width /= sizeof(int); /* set width in ints */
73 swap_func = swap_ints; /* use int swap function */
74 }
75 #endif
76
77 base = (char *)basep; /* set up char * base pointer */
78 thresh = T * size; /* init threshold */
79 sp = stack; /* init stack pointer */
80 limit = base + nelems * size;/* pointer past end of array */
81
82 while (1)
83 {
84 /* repeat until break... */
85 if (limit > base + thresh)
86 {
87 /* if more than T elements, swap base with middle */
88 SWAP((((limit-base)/size)/2)*size+base, base);
89
90 i = base + size; /* i scans left to right */
91 j = limit - size; /* j scans right to left */
92 if (COMP(i, j, cd) > 0) /* Sedgewick's */
93 SWAP(i, j); /* three-element sort */
94 if (COMP(base, j, cd) > 0)/* sets things up */
95 SWAP(base, j); /* so that */
96 if (COMP(i, base,cd ) > 0)/* *i <= *base <= *j */
97 SWAP(i, base); /* *base is pivot element */
98
99 while (1)
100 {
101 do
102 {
103 /* move i right until *i >= pivot */
104 i += size;
105 }
106 while (COMP(i, base, cd) < 0);
107
108 /* move j left until *j <= pivot */
109 do
110 {
111 j -= size;
112 }
113 while (COMP(j, base, cd) > 0);
114
115 /* if pointers crossed, break loop */
116 if (i > j) break;
117
118 SWAP(i, j); /* else swap elements, keep scanning*/
119 }
120
121 SWAP(base, j); /* move pivot into correct place */
122
123 if (j - base > limit - i)
124 {
125 /* if left subfile larger */
126 sp[0] = base; /* stack left subfile base */
127 sp[1] = j; /* and limit */
128 base = i; /* sort the right subfile */
129 }
130 else
131 {
132 /* else right subfile larger*/
133 sp[0] = i; /* stack right subfile base */
134 sp[1] = limit; /* and limit */
135 limit = j; /* sort the left subfile */
136 }
137 sp += 2; /* increment stack pointer */
138 }
139 else
140 {
141 /* else subfile is small, use insertion sort */
142 j = base;
143 i = j + size;
144
145 while (i < limit)
146 {
147 while (COMP(j, j + size, cd) > 0)
148 {
149 SWAP(j, j+size);
150 if (j == base)
151 break;
152 j -= size;
153 }
154
155 j = i;
156 i += size;
157 }
158
159 if (sp == stack) /* done */
160 break;
161
162 /* if any entries on stack */
163 sp -= 2; /* pop the base and limit */
164 base = sp[0];
165 limit = sp[1];
166 }
167 }
168 }
169
170 /*
171 ** swap nbytes between a and b
172 */
173
swap_chars(char * a,char * b,size_t nbytes)174 static void swap_chars(char *a, char *b, size_t nbytes)
175 {
176 char tmp;
177 do
178 {
179 tmp = *a; *a++ = *b; *b++ = tmp;
180 }
181 while ( --nbytes );
182 }
183
184 #ifdef SWAP_INTS
185
186 /*
187 ** swap nints between a and b
188 */
189
swap_ints(char * ap,char * bp,size_t nints)190 static void swap_ints(char *ap, char *bp, size_t nints)
191 {
192 int *a = (int *)ap, *b = (int *)bp;
193 int tmp;
194 do
195 {
196 tmp = *a; *a++ = *b; *b++ = tmp;
197 }
198 while ( --nints );
199 }
200
201 #endif
202
203 #ifdef TESTING
204
205 #include <stdio.h>
206 #include <math.h>
207
cmp_fun(void * a,void * b,void * c)208 static int cmp_fun (void *a, void *b, void *c)
209 {
210 double x, y;
211 double *xp, *yp;
212 double *data;
213
214 data = (double *) c;
215
216 xp = data + *(unsigned int *)a;
217 yp = data + *(unsigned int *)b;
218
219 x = *xp;
220 y = *yp;
221
222 if (x > y) return 1; else if (x < y) return -1;
223 if (xp > yp) return 1;
224 if (xp == yp) return 0;
225 return -1;
226 }
227
228 #define ARRAY_SIZE 10000
main(int argc,char ** argv)229 int main (int argc, char **argv)
230 {
231 unsigned int i;
232 double x, dx;
233 unsigned int index_array [ARRAY_SIZE];
234 double double_array [ARRAY_SIZE];
235
236 x = 0.0;
237 dx = 6.28 / ARRAY_SIZE;
238 for (i = 0; i < ARRAY_SIZE; i++)
239 {
240 double_array [i] = sin(x);
241 index_array [i] = i;
242 x += dx;
243 }
244
245 _SLqsort ((void *) index_array, ARRAY_SIZE,
246 sizeof (unsigned int), cmp_fun, (void *) double_array);
247
248 if (argc > 1)
249 for (i = 0; i < ARRAY_SIZE; i++)
250 {
251 fprintf (stdout, "%f\t%f\n",
252 double_array[i], double_array[index_array[i]]);
253 }
254
255 return 0;
256 }
257 #endif
258