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 <stdexcept>
40 
41 #include <climits>
42 
43 namespace libcoyotl
44 {
45 
46  //--------------------------------------------------
47  // sort two items
48 
49  template<class T>
50  inline void sort_two(T & a, T & b)
51  {
52  if (a > b)
53  {
54  T t = a;
55  a = b;
56  b = t;
57  }
58  }
59 
60  //--------------------------------------------------
61  // sort three items
62 
63  template<class T>
64  inline void sort_three(T & a, T & b, T & c)
65  {
66  sort_two(a,b);
67  sort_two(a,c);
68  sort_two(b,c);
69  }
70 
71  //--------------------------------------------------
72  // shell sort an array in ascending order
73 
74  template<class T> void
75  shell_sort(T * a, size_t n)
76  {
77  size_t inc, i, j;
78  T t;
79 
80  // algorithm relies on one-based arrays
81  --a;
82 
83  for (inc = 1; inc <= n / 9; inc = 3 * inc + 1) ;
84 
85  for ( ; inc > 0; inc /= 3)
86  {
87  for (i = inc + 1; i <= n; i += inc)
88  {
89  t = a[i];
90  j = i;
91 
92  while ((j > inc) && (a[j - inc] > t))
93  {
94  a[j] = a[j - inc];
95  j -= inc;
96  }
97 
98  a[j] = t;
99  }
100  }
101  }
102 
103  //--------------------------------------------------
104  // shell sort an array in ascending order
105 
106  template<class T>
107  void shell_sort_descending(T * array, size_t n)
108  {
109  size_t increment, i, j;
110  T t;
111 
112  // algorithm relies on one-based arrays
113  --array;
114 
115  for (increment = 1; increment <= n / 9; increment = 3 * increment + 1) ;
116 
117  for ( ; increment > 0; increment /= 3)
118  {
119  for (i = increment + 1; i <= n; i += increment)
120  {
121  t = array[i];
122  j = i;
123 
124  while ((j > increment) && (array[j - increment] < t))
125  {
126  array[j] = array[j - increment];
127  j -= increment;
128  }
129 
130  array[j] = t;
131  }
132  }
133  }
134 
135  //--------------------------------------------------
136  // Quick Sort an array in ascending order
137  template <class T>
138  void quick_sort(T * array, size_t n)
139  {
140  static const size_t STACK_SIZE = CHAR_BIT * sizeof(int);
141  static const size_t THRESHOLD = 7;
142 
143  size_t left_index = 0;
144  size_t right_index = n - 1;
145 
146  T temp, pivot;
147  size_t scan_left, scan_right, middle, pivot_index, size_left, size_right;
148  size_t stack_left[STACK_SIZE], stack_right[STACK_SIZE], stack_ptr = 0;
149 
150  while (true)
151  {
152  while (right_index > left_index)
153  {
154  if ((right_index - left_index) > THRESHOLD)
155  {
156  // "median-of-three" partitioning
157  middle = (left_index + right_index) / 2;
158 
159  // three-sort left, middle, and right elements
160  if (array[left_index] > array[middle])
161  {
162  temp = array[left_index];
163  array[left_index] = array[middle];
164  array[middle] = temp;
165  }
166 
167  if (array[left_index] > array[right_index])
168  {
169  temp = array[left_index];
170  array[left_index] = array[right_index];
171  array[right_index] = temp;
172  }
173 
174  if (array[middle] > array[right_index])
175  {
176  temp = array[middle];
177  array[middle] = array[right_index];
178  array[right_index] = temp;
179  }
180 
181  pivot_index = right_index - 1;
182 
183  temp = array[middle];
184  array[middle] = array[pivot_index];
185  array[pivot_index] = temp;
186 
187  // set-up for partitioning
188  scan_left = left_index + 1;
189  scan_right = right_index - 2;
190  }
191  else
192  {
193  pivot_index = right_index;
194  scan_left = left_index;
195  scan_right = right_index - 1;
196  }
197 
198  pivot = array[pivot_index];
199 
200  while (true)
201  {
202  // scan from left
203  while ((array[scan_left] < pivot) && (scan_left < right_index))
204  ++scan_left;
205 
206  // scan from right
207  while ((array[scan_right] > pivot) && (scan_right > left_index))
208  --scan_right;
209 
210  // if scans have met, exit inner loop
211  if (scan_left >= scan_right)
212  break;
213 
214  // exchange elements
215  temp = array[scan_right];
216  array[scan_right] = array[scan_left];
217  array[scan_left] = temp;
218 
219  if (scan_left < right_index)
220  ++scan_left;
221 
222  if (scan_right > left_index)
223  --scan_right;
224  }
225 
226  // exchange final element
227  if (scan_left != pivot_index)
228  {
229  temp = array[pivot_index];
230  array[pivot_index] = array[scan_left];
231  array[scan_left] = temp;
232  }
233 
234  // place largest partition on stack
235  size_left = scan_left - left_index;
236  size_right = right_index - scan_left;
237 
238  if (size_left > size_right)
239  {
240  if (size_left != 1)
241  {
242  ++stack_ptr;
243 
244  if (stack_ptr == STACK_SIZE)
245  throw std::runtime_error("stack overflow in quick_sort");
246 
247  stack_left[stack_ptr] = left_index;
248  stack_right[stack_ptr] = scan_left - 1;
249  }
250 
251  if (size_right != 0)
252  left_index = scan_left + 1;
253  else
254  break;
255  }
256  else
257  {
258  if (size_right != 1)
259  {
260  ++stack_ptr;
261 
262  if (stack_ptr == STACK_SIZE)
263  throw std::runtime_error("stack overflow in quick_sort");
264 
265  stack_left[stack_ptr] = scan_left + 1;
266  stack_right[stack_ptr] = right_index;
267  }
268 
269  if (size_left != 0)
270  right_index = scan_left - 1;
271  else
272  break;
273  }
274  }
275 
276  // iterate with values from stack
277  if (stack_ptr > 0)
278  {
279  left_index = stack_left[stack_ptr];
280  right_index = stack_right[stack_ptr];
281 
282  --stack_ptr;
283  }
284  else
285  break;
286  }
287  }
288 
289 } // end namespace libcoyotl
290 
291 #endif
292 

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