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 
42 namespace 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.