Commit | Line | Data |
---|---|---|
34849bd9 KB |
1 | /*- |
2 | * Copyright (c) 1990 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * %sccs.include.redist.c% | |
6 | */ | |
7 | ||
8 | #if defined(LIBC_SCCS) && !defined(lint) | |
33f8130f | 9 | static char sccsid[] = "@(#)radixsort.c 5.6 (Berkeley) %G%"; |
34849bd9 KB |
10 | #endif /* LIBC_SCCS and not lint */ |
11 | ||
12 | #include <sys/types.h> | |
34849bd9 KB |
13 | #include <limits.h> |
14 | #include <stdlib.h> | |
15 | #include <stddef.h> | |
16 | ||
34849bd9 | 17 | /* |
34849bd9 KB |
18 | * __rspartition is the cutoff point for a further partitioning instead |
19 | * of a shellsort. If it changes check __rsshell_increments. Both of | |
33f8130f | 20 | * these are exported, as the best values are data dependent. |
34849bd9 KB |
21 | */ |
22 | #define NPARTITION 40 | |
23 | int __rspartition = NPARTITION; | |
24 | int __rsshell_increments[] = { 4, 1, 0, 0, 0, 0, 0, 0 }; | |
34849bd9 KB |
25 | |
26 | /* | |
dfad239c KB |
27 | * Stackp points to context structures, where each structure schedules a |
28 | * partitioning. Radixsort exits when the stack is empty. | |
34849bd9 | 29 | * |
a5baf581 | 30 | * If the buckets are placed on the stack randomly, the worst case is when |
e061e641 | 31 | * all the buckets but one contain (npartitions + 1) elements and the bucket |
a5baf581 KB |
32 | * pushed on the stack last contains the rest of the elements. In this case, |
33 | * stack growth is bounded by: | |
dfad239c | 34 | * |
e061e641 KB |
35 | * limit = (nelements / (npartitions + 1)) - 1; |
36 | * | |
37 | * This is a very large number, 52,377,648 for the maximum 32-bit signed int. | |
dfad239c | 38 | * |
e061e641 KB |
39 | * By forcing the largest bucket to be pushed on the stack first, the worst |
40 | * case is when all but two buckets each contain (npartitions + 1) elements, | |
41 | * with the remaining elements split equally between the first and last | |
42 | * buckets pushed on the stack. In this case, stack growth is bounded when: | |
dfad239c | 43 | * |
a5baf581 | 44 | * for (partition_cnt = 0; nelements > npartitions; ++partition_cnt) |
dfad239c KB |
45 | * nelements = |
46 | * (nelements - (npartitions + 1) * (nbuckets - 2)) / 2; | |
47 | * The bound is: | |
48 | * | |
49 | * limit = partition_cnt * (nbuckets - 1); | |
a5baf581 | 50 | * |
e061e641 | 51 | * This is a much smaller number, 4590 for the maximum 32-bit signed int. |
34849bd9 | 52 | */ |
e061e641 KB |
53 | #define NBUCKETS (UCHAR_MAX + 1) |
54 | ||
34849bd9 KB |
55 | typedef struct _stack { |
56 | u_char **bot; | |
57 | int indx, nmemb; | |
58 | } CONTEXT; | |
59 | ||
34849bd9 | 60 | #define STACKPUSH { \ |
34849bd9 KB |
61 | stackp->bot = p; \ |
62 | stackp->nmemb = nmemb; \ | |
63 | stackp->indx = indx; \ | |
64 | ++stackp; \ | |
65 | } | |
34849bd9 KB |
66 | #define STACKPOP { \ |
67 | if (stackp == stack) \ | |
68 | break; \ | |
69 | --stackp; \ | |
70 | bot = stackp->bot; \ | |
71 | nmemb = stackp->nmemb; \ | |
72 | indx = stackp->indx; \ | |
73 | } | |
74 | ||
75 | /* | |
76 | * A variant of MSD radix sorting; see Knuth Vol. 3, page 177, and 5.2.5, | |
dfad239c KB |
77 | * Ex. 10 and 12. Also, "Three Partition Refinement Algorithms, Paige |
78 | * and Tarjan, SIAM J. Comput. Vol. 16, No. 6, December 1987. | |
34849bd9 | 79 | * |
dfad239c KB |
80 | * This uses a simple sort as soon as a bucket crosses a cutoff point, |
81 | * rather than sorting the entire list after partitioning is finished. | |
82 | * This should be an advantage. | |
34849bd9 | 83 | * |
dfad239c KB |
84 | * This is pure MSD instead of LSD of some number of MSD, switching to |
85 | * the simple sort as soon as possible. Takes linear time relative to | |
86 | * the number of bytes in the strings. | |
34849bd9 KB |
87 | */ |
88 | radixsort(l1, nmemb, tab, endbyte) | |
89 | u_char **l1, *tab, endbyte; | |
90 | register int nmemb; | |
91 | { | |
92 | register int i, indx, t1, t2; | |
93 | register u_char **l2, **p, **bot, *tr; | |
dfad239c | 94 | CONTEXT *stack, *stackp; |
e061e641 KB |
95 | int c[NBUCKETS + 1], max; |
96 | u_char ltab[NBUCKETS]; | |
33f8130f | 97 | static void shellsort(); |
34849bd9 KB |
98 | |
99 | if (nmemb <= 1) | |
100 | return(0); | |
101 | ||
a5baf581 | 102 | /* |
dfad239c KB |
103 | * T1 is the constant part of the equation, the number of elements |
104 | * represented on the stack between the top and bottom entries. | |
a5baf581 KB |
105 | * It doesn't get rounded as the divide by 2 rounds down (correct |
106 | * for a value being subtracted). T2, the nelem value, has to be | |
107 | * rounded up before each divide because we want an upper bound; | |
108 | * this could overflow if nmemb is the maximum int. | |
109 | */ | |
e061e641 KB |
110 | t1 = ((__rspartition + 1) * (NBUCKETS - 2)) >> 1; |
111 | for (i = 0, t2 = nmemb; t2 > __rspartition; i += NBUCKETS - 1) | |
5fa271fa | 112 | t2 = ((t2 + 1) >> 1) - t1; |
dfad239c | 113 | if (i) { |
a5baf581 | 114 | if (!(stack = stackp = (CONTEXT *)malloc(i * sizeof(CONTEXT)))) |
dfad239c KB |
115 | return(-1); |
116 | } else | |
117 | stack = stackp = NULL; | |
118 | ||
34849bd9 | 119 | /* |
dfad239c | 120 | * There are two arrays, one provided by the user (l1), and the |
34849bd9 KB |
121 | * temporary one (l2). The data is sorted to the temporary stack, |
122 | * and then copied back. The speedup of using index to determine | |
123 | * which stack the data is on and simply swapping stacks back and | |
124 | * forth, thus avoiding the copy every iteration, turns out to not | |
125 | * be any faster than the current implementation. | |
126 | */ | |
127 | if (!(l2 = (u_char **)malloc(sizeof(u_char *) * nmemb))) | |
128 | return(-1); | |
129 | ||
34849bd9 | 130 | /* |
dfad239c | 131 | * Tr references a table of sort weights; multiple entries may |
34849bd9 KB |
132 | * map to the same weight; EOS char must have the lowest weight. |
133 | */ | |
134 | if (tab) | |
135 | tr = tab; | |
136 | else { | |
137 | tr = ltab; | |
138 | for (t1 = 0, t2 = endbyte; t1 < t2; ++t1) | |
139 | tr[t1] = t1 + 1; | |
140 | tr[t2] = 0; | |
e061e641 | 141 | for (t1 = endbyte + 1; t1 < NBUCKETS; ++t1) |
34849bd9 KB |
142 | tr[t1] = t1; |
143 | } | |
144 | ||
dfad239c | 145 | /* First sort is entire stack */ |
34849bd9 KB |
146 | bot = l1; |
147 | indx = 0; | |
148 | ||
149 | for (;;) { | |
dfad239c | 150 | /* Clear bucket count array */ |
34849bd9 KB |
151 | bzero((char *)c, sizeof(c)); |
152 | ||
153 | /* | |
dfad239c | 154 | * Compute number of items that sort to the same bucket |
34849bd9 KB |
155 | * for this index. |
156 | */ | |
33f8130f | 157 | for (p = bot, i = nmemb; --i >= 0;) |
34849bd9 KB |
158 | ++c[tr[(*p++)[indx]]]; |
159 | ||
160 | /* | |
dfad239c | 161 | * Sum the number of characters into c, dividing the temp |
34849bd9 KB |
162 | * stack into the right number of buckets for this bucket, |
163 | * this index. C contains the cumulative total of keys | |
164 | * before and included in this bucket, and will later be | |
e061e641 | 165 | * used as an index to the bucket. c[NBUCKETS] contains |
34849bd9 | 166 | * the total number of elements, for determining how many |
dfad239c | 167 | * elements the last bucket contains. At the same time |
e061e641 | 168 | * find the largest bucket so it gets pushed first. |
34849bd9 | 169 | */ |
e061e641 KB |
170 | for (i = max = t1 = 0, t2 = __rspartition; i <= NBUCKETS; ++i) { |
171 | if (c[i] > t2) { | |
172 | t2 = c[i]; | |
dfad239c KB |
173 | max = i; |
174 | } | |
e061e641 | 175 | t1 = c[i] += t1; |
dfad239c | 176 | } |
34849bd9 KB |
177 | |
178 | /* | |
e061e641 KB |
179 | * Partition the elements into buckets; c decrements through |
180 | * the bucket, and ends up pointing to the first element of | |
181 | * the bucket. | |
34849bd9 | 182 | */ |
33f8130f | 183 | for (i = nmemb; --i >= 0;) { |
34849bd9 KB |
184 | --p; |
185 | l2[--c[tr[(*p)[indx]]]] = *p; | |
186 | } | |
187 | ||
dfad239c | 188 | /* Copy the partitioned elements back to user stack */ |
34849bd9 KB |
189 | bcopy(l2, bot, nmemb * sizeof(u_char *)); |
190 | ||
191 | ++indx; | |
192 | /* | |
dfad239c | 193 | * Sort buckets as necessary; don't sort c[0], it's the |
34849bd9 KB |
194 | * EOS character bucket, and nothing can follow EOS. |
195 | */ | |
dfad239c KB |
196 | for (i = max; i; --i) { |
197 | if ((nmemb = c[i + 1] - (t1 = c[i])) < 2) | |
198 | continue; | |
199 | p = bot + t1; | |
200 | if (nmemb > __rspartition) | |
201 | STACKPUSH | |
202 | else | |
33f8130f | 203 | shellsort(p, indx, nmemb, tr); |
dfad239c | 204 | } |
e061e641 | 205 | for (i = max + 1; i < NBUCKETS; ++i) { |
34849bd9 KB |
206 | if ((nmemb = c[i + 1] - (t1 = c[i])) < 2) |
207 | continue; | |
208 | p = bot + t1; | |
209 | if (nmemb > __rspartition) | |
210 | STACKPUSH | |
211 | else | |
33f8130f | 212 | shellsort(p, indx, nmemb, tr); |
34849bd9 | 213 | } |
dfad239c | 214 | /* Break out when stack is empty */ |
34849bd9 KB |
215 | STACKPOP |
216 | } | |
217 | ||
218 | free((char *)l2); | |
219 | free((char *)stack); | |
34849bd9 KB |
220 | return(0); |
221 | } | |
33f8130f KB |
222 | |
223 | /* | |
224 | * Shellsort (diminishing increment sort) from Data Structures and | |
225 | * Algorithms, Aho, Hopcraft and Ullman, 1983 Edition, page 290; | |
226 | * see also Knuth Vol. 3, page 84. The increments are selected from | |
227 | * formula (8), page 95. Roughly O(N^3/2). | |
228 | */ | |
229 | static void | |
230 | shellsort(p, indx, nmemb, tr) | |
231 | register u_char **p, *tr; | |
232 | register int indx, nmemb; | |
233 | { | |
234 | register u_char ch, *s1, *s2; | |
235 | register int incr, *incrp, t1, t2; | |
236 | ||
237 | for (incrp = __rsshell_increments; incr = *incrp++;) | |
238 | for (t1 = incr; t1 < nmemb; ++t1) | |
239 | for (t2 = t1 - incr; t2 >= 0;) { | |
240 | s1 = p[t2] + indx; | |
241 | s2 = p[t2 + incr] + indx; | |
242 | while ((ch = tr[*s1++]) == tr[*s2] && ch) | |
243 | ++s2; | |
244 | if (ch > tr[*s2]) { | |
245 | s1 = p[t2]; | |
246 | p[t2] = p[t2 + incr]; | |
247 | p[t2 + incr] = s1; | |
248 | t2 -= incr; | |
249 | } else | |
250 | break; | |
251 | } | |
252 | } |