libcoyotl - A Library of C++ Tools

Created by Scott Robert Ladd at Coyote Gulch Productions.


sortutil.h
1//---------------------------------------------------------------------
2// Algorithmic Conjurings @ http://www.coyotegulch.com
3//
4// sortutil.h
5//
6// Generic tools for sorting C-type arrays of data.
7//---------------------------------------------------------------------
8//
9// Copyright 1990-2005 Scott Robert Ladd
10//
11// This program is free software; you can redistribute it and/or modify
12// it under the terms of the GNU General Public License as published by
13// the Free Software Foundation; either version 2 of the License, or
14// (at your option) any later version.
15//
16// This program is distributed in the hope that it will be useful,
17// but WITHOUT ANY WARRANTY; without even the implied warranty of
18// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19// GNU General Public License for more details.
20//
21// You should have received a copy of the GNU General Public License
22// along with this program; if not, write to the
23// Free Software Foundation, Inc.
24// 59 Temple Place - Suite 330
25// Boston, MA 02111-1307, USA.
26//
27//-----------------------------------------------------------------------
28//
29// For more information on this software package, please visit
30// Scott's web site, Coyote Gulch Productions, at:
31//
32// http://www.coyotegulch.com
33//
34//-----------------------------------------------------------------------
35
36#if !defined(LIBCOYOTL_SORTUTIL_H)
37#define LIBCOYOTL_SORTUTIL_H
38
39#include <climits>
40#include <stdexcept>
41
42namespace libcoyotl
43{
44
45 //--------------------------------------------------
46 // sort two items
47
48 template<class T>
49 inline void sort_two(T & a, T & b)
50 {
51 if (a > b)
52 {
53 T t = a;
54 a = b;
55 b = t;
56 }
57 }
58
59 //--------------------------------------------------
60 // sort three items
61
62 template<class T>
63 inline void sort_three(T & a, T & b, T & c)
64 {
65 sort_two(a,b);
66 sort_two(a,c);
67 sort_two(b,c);
68 }
69
70 //--------------------------------------------------
71 // shell sort an array in ascending order
72
73 template<class T> void
74 shell_sort(T * a, size_t n)
75 {
76 size_t inc, i, j;
77 T t;
78
79 // algorithm relies on one-based arrays
80 --a;
81
82 for (inc = 1; inc <= n / 9; inc = 3 * inc + 1) ;
83
84 for ( ; inc > 0; inc /= 3)
85 {
86 for (i = inc + 1; i <= n; i += inc)
87 {
88 t = a[i];
89 j = i;
90
91 while ((j > inc) && (a[j - inc] > t))
92 {
93 a[j] = a[j - inc];
94 j -= inc;
95 }
96
97 a[j] = t;
98 }
99 }
100 }
101
102 //--------------------------------------------------
103 // shell sort an array in ascending order
104
105 template<class T>
106 void shell_sort_descending(T * array, size_t n)
107 {
108 size_t increment, i, j;
109 T t;
110
111 // algorithm relies on one-based arrays
112 --array;
113
114 for (increment = 1; increment <= n / 9; increment = 3 * increment + 1) ;
115
116 for ( ; increment > 0; increment /= 3)
117 {
118 for (i = increment + 1; i <= n; i += increment)
119 {
120 t = array[i];
121 j = i;
122
123 while ((j > increment) && (array[j - increment] < t))
124 {
125 array[j] = array[j - increment];
126 j -= increment;
127 }
128
129 array[j] = t;
130 }
131 }
132 }
133
134 //--------------------------------------------------
135 // Quick Sort an array in ascending order
136 template <class T>
137 void quick_sort(T * array, size_t n)
138 {
139 static const size_t STACK_SIZE = CHAR_BIT * sizeof(int);
140 static const size_t THRESHOLD = 7;
141
142 size_t left_index = 0;
143 size_t right_index = n - 1;
144
145 T temp, pivot;
146 size_t scan_left, scan_right, middle, pivot_index, size_left, size_right;
147 size_t stack_left[STACK_SIZE], stack_right[STACK_SIZE], stack_ptr = 0;
148
149 while (true)
150 {
151 while (right_index > left_index)
152 {
153 if ((right_index - left_index) > THRESHOLD)
154 {
155 // "median-of-three" partitioning
156 middle = (left_index + right_index) / 2;
157
158 // three-sort left, middle, and right elements
159 if (array[left_index] > array[middle])
160 {
161 temp = array[left_index];
162 array[left_index] = array[middle];
163 array[middle] = temp;
164 }
165
166 if (array[left_index] > array[right_index])
167 {
168 temp = array[left_index];
169 array[left_index] = array[right_index];
170 array[right_index] = temp;
171 }
172
173 if (array[middle] > array[right_index])
174 {
175 temp = array[middle];
176 array[middle] = array[right_index];
177 array[right_index] = temp;
178 }
179
180 pivot_index = right_index - 1;
181
182 temp = array[middle];
183 array[middle] = array[pivot_index];
184 array[pivot_index] = temp;
185
186 // set-up for partitioning
187 scan_left = left_index + 1;
188 scan_right = right_index - 2;
189 }
190 else
191 {
192 pivot_index = right_index;
193 scan_left = left_index;
194 scan_right = right_index - 1;
195 }
196
197 pivot = array[pivot_index];
198
199 while (true)
200 {
201 // scan from left
202 while ((array[scan_left] < pivot) && (scan_left < right_index))
203 ++scan_left;
204
205 // scan from right
206 while ((array[scan_right] > pivot) && (scan_right > left_index))
207 --scan_right;
208
209 // if scans have met, exit inner loop
210 if (scan_left >= scan_right)
211 break;
212
213 // exchange elements
214 temp = array[scan_right];
215 array[scan_right] = array[scan_left];
216 array[scan_left] = temp;
217
218 if (scan_left < right_index)
219 ++scan_left;
220
221 if (scan_right > left_index)
222 --scan_right;
223 }
224
225 // exchange final element
226 if (scan_left != pivot_index)
227 {
228 temp = array[pivot_index];
229 array[pivot_index] = array[scan_left];
230 array[scan_left] = temp;
231 }
232
233 // place largest partition on stack
234 size_left = scan_left - left_index;
235 size_right = right_index - scan_left;
236
237 if (size_left > size_right)
238 {
239 if (size_left != 1)
240 {
241 ++stack_ptr;
242
243 if (stack_ptr == STACK_SIZE)
244 throw std::runtime_error("stack overflow in quick_sort");
245
246 stack_left[stack_ptr] = left_index;
247 stack_right[stack_ptr] = scan_left - 1;
248 }
249
250 if (size_right != 0)
251 left_index = scan_left + 1;
252 else
253 break;
254 }
255 else
256 {
257 if (size_right != 1)
258 {
259 ++stack_ptr;
260
261 if (stack_ptr == STACK_SIZE)
262 throw std::runtime_error("stack overflow in quick_sort");
263
264 stack_left[stack_ptr] = scan_left + 1;
265 stack_right[stack_ptr] = right_index;
266 }
267
268 if (size_left != 0)
269 right_index = scan_left - 1;
270 else
271 break;
272 }
273 }
274
275 // iterate with values from stack
276 if (stack_ptr > 0)
277 {
278 left_index = stack_left[stack_ptr];
279 right_index = stack_right[stack_ptr];
280
281 --stack_ptr;
282 }
283 else
284 break;
285 }
286 }
287
288} // end namespace libcoyotl
289
290#endif
291

© 1996-2005 Scott Robert Ladd. All rights reserved.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.