1 /*
2 ** Sorting stuff by Dann Corbit and Pete Filandr.
3 ** (dcorbit@connx.com and pfilandr@mindspring.com)
4 ** Use it however you like.
5 */
6 
7 //
8 //  The insertion sort template is used for small partitions.
9 //  Insertion sort is stable.
10 //
11 
12 template < class e_type >
insertion_sort(e_type * array,size_t nmemb)13 void insertion_sort(e_type * array, size_t nmemb)
14 {
15     e_type temp,
16           *last,
17           *first,
18           *middle;
19     if (nmemb > 1) {
20         first = middle = 1 + array;
21         last = nmemb - 1 + array;
22         while (first != last) {
23             ++first;
24             if ((*(middle) > *(first))) {
25                 middle = first;
26             }
27         }
28         if ((*(array) > *(middle))) {
29             ((void) ((temp) = *(array), *(array) = *(middle), *(middle) = (temp)));
30         }
31         ++array;
32         while (array != last) {
33             first = array++;
34             if ((*(first) > *(array))) {
35                 middle = array;
36                 temp = *middle;
37                 do {
38                     *middle-- = *first--;
39                 } while ((*(first) > *(&temp)));
40                 *middle = temp;
41             }
42         }
43     }
44 }
45 
46 //
47 // The median estimate is used to choose pivots for the quicksort algorithm
48 //
49 
50 template < class e_type >
median_estimate(e_type * array,size_t n)51 void median_estimate(e_type * array, size_t n)
52 {
53     e_type          temp;
54     long unsigned   lu_seed = 123456789LU;
55     const size_t    k = ((lu_seed) = 69069 * (lu_seed) + 362437) % --n;
56     ((void) ((temp) = *(array), *(array) = *(array + k), *(array + k) = (temp)));
57     if ((*((array + 1)) > *((array)))) {
58         (temp) = *(array + 1);
59         if ((*((array + n)) > *((array)))) {
60             *(array + 1) = *(array);
61             if ((*(&(temp)) > *((array + n)))) {
62                 *(array) = *(array + n);
63                 *(array + n) = (temp);
64             } else {
65                 *(array) = (temp);
66             }
67         } else {
68             *(array + 1) = *(array + n);
69             *(array + n) = (temp);
70         }
71     } else {
72         if ((*((array)) > *((array + n)))) {
73             if ((*((array + 1)) > *((array + n)))) {
74                 (temp) = *(array + 1);
75                 *(array + 1) = *(array + n);
76                 *(array + n) = *(array);
77                 *(array) = (temp);
78             } else {
79                 ((void) (((temp)) = *((array)), *((array)) = *((array + n)), *((array + n)) = ((temp))));
80             }
81         }
82     }
83 }
84 
85 
86 //
87 // This is the heart of the quick sort algorithm used here.
88 // If the sort is going quadratic, we switch to heap sort.
89 // If the partition is small, we switch to insertion sort.
90 //
91 
92 template < class e_type >
qloop(e_type * array,size_t nmemb,size_t d)93 void qloop(e_type * array, size_t nmemb, size_t d)
94 {
95     e_type temp,
96           *first,
97           *last;
98     while (nmemb > 50) {
99         if (sorted(array, nmemb)) {
100             return;
101         }
102         if (!d--) {
103             heapsort(array, nmemb);
104             return;
105         }
106         median_estimate(array, nmemb);
107         first = 1 + array;
108         last = nmemb - 1 + array;
109         do {
110             ++first;
111         } while ((*(array) > *(first)));
112         do {
113             --last;
114         } while ((*(last) > *(array)));
115         while (last > first) {
116             ((void) ((temp) = *(last), *(last) = *(first), *(first) = (temp)));
117             do {
118                 ++first;
119             } while ((*(array) > *(first)));
120             do {
121                 --last;
122             } while ((*(last) > *(array)));
123         }
124         ((void) ((temp) = *(array), *(array) = *(last), *(last) = (temp)));
125         qloop(last + 1, nmemb - 1 + array - last, d);
126         nmemb = last - array;
127     }
128     insertion_sort(array, nmemb);
129 }
130 
131 //
132 // This heap sort is better than average because it uses Lamont's heap.
133 //
134 
135 template < class e_type >
heapsort(e_type * array,size_t nmemb)136 void heapsort(e_type * array, size_t nmemb)
137 {
138     size_t i,
139            child,
140            parent;
141     e_type temp;
142     if (nmemb > 1) {
143         i = --nmemb / 2;
144         do {
145             {
146                 (parent) = (i);
147                 (temp) = (array)[(parent)];
148                 (child) = (parent) * 2;
149                 while ((nmemb) > (child)) {
150                     if ((*((array) + (child) + 1) > *((array) + (child)))) {
151                         ++(child);
152                     }
153                     if ((*((array) + (child)) > *(&(temp)))) {
154                         (array)[(parent)] = (array)[(child)];
155                         (parent) = (child);
156                         (child) *= 2;
157                     } else {
158                         --(child);
159                         break;
160                     }
161                 }
162                 if ((nmemb) == (child) && (*((array) + (child)) > *(&(temp)))) {
163                     (array)[(parent)] = (array)[(child)];
164                     (parent) = (child);
165                 }
166                 (array)[(parent)] = (temp);
167             }
168         } while (i--);
169         ((void) ((temp) = *(array), *(array) = *(array + nmemb), *(array + nmemb) = (temp)));
170         for (--nmemb; nmemb; --nmemb) {
171             {
172                 (parent) = (0);
173                 (temp) = (array)[(parent)];
174                 (child) = (parent) * 2;
175                 while ((nmemb) > (child)) {
176                     if ((*((array) + (child) + 1) > *((array) + (child)))) {
177                         ++(child);
178                     }
179                     if ((*((array) + (child)) > *(&(temp)))) {
180                         (array)[(parent)] = (array)[(child)];
181                         (parent) = (child);
182                         (child) *= 2;
183                     } else {
184                         --(child);
185                         break;
186                     }
187                 }
188                 if ((nmemb) == (child) && (*((array) + (child)) > *(&(temp)))) {
189                     (array)[(parent)] = (array)[(child)];
190                     (parent) = (child);
191                 }
192                 (array)[(parent)] = (temp);
193             }
194             ((void) ((temp) = *(array), *(array) = *(array + nmemb), *(array + nmemb) = (temp)));
195         }
196     }
197 }
198 
199 //
200 // We use this to check to see if a partition is already sorted.
201 //
202 
203 template < class e_type >
sorted(e_type * array,size_t nmemb)204 int sorted(e_type * array, size_t nmemb)
205 {
206     for (--nmemb; nmemb; --nmemb) {
207         if ((*(array) > *(array + 1))) {
208             return 0;
209         }
210         ++array;
211     }
212     return 1;
213 }
214 
215 //
216 // We use this to check to see if a partition is already reverse-sorted.
217 //
218 
219 template < class e_type >
rev_sorted(e_type * array,size_t nmemb)220 int             rev_sorted(e_type * array, size_t nmemb)
221 {
222     for (--nmemb; nmemb; --nmemb) {
223         if ((*(array + 1) > *(array))) {
224             return 0;
225         }
226         ++array;
227     }
228     return 1;
229 }
230 
231 //
232 // We use this to reverse a reverse-sorted partition.
233 //
234 
235 template < class e_type >
rev_array(e_type * array,size_t nmemb)236 void rev_array(e_type * array, size_t nmemb)
237 {
238     e_type          temp,
239         *end;
240     for (end = array + nmemb - 1; end > array; ++array) {
241         ((void) ((temp) = *(array), *(array) = *(end), *(end) = (temp)));
242         --end;
243     }
244 }
245 
246 //
247 // Introspective quick sort algorithm user entry point.
248 // You do not need to directly call any other sorting template.
249 // This sort will perform very well under all circumstances.
250 //
251 
252 template < class e_type >
iqsort(e_type * array,size_t nmemb)253 void iqsort(e_type * array, size_t nmemb)
254 {
255     size_t d,
256            n;
257     if (nmemb > 1 && !sorted(array, nmemb)) {
258         if (!rev_sorted(array, nmemb)) {
259             n = nmemb / 4;
260             d = 2;
261             while (n) {
262                 ++d;
263                 n /= 2;
264             }
265             qloop(array, nmemb, 2 * d);
266         } else {
267             rev_array(array, nmemb);
268         }
269     }
270 }
271 
272