36 #if !defined(LIBCOYOTL_SORTUTIL_H)
37 #define LIBCOYOTL_SORTUTIL_H
49 inline void sort_two(T & a, T & b)
63 inline void sort_three(T & a, T & b, T & c)
73 template<
class T>
void
74 shell_sort(T * a,
size_t n)
82 for (inc = 1; inc <= n / 9; inc = 3 * inc + 1) ;
84 for ( ; inc > 0; inc /= 3)
86 for (i = inc + 1; i <= n; i += inc)
91 while ((j > inc) && (a[j - inc] > t))
106 void shell_sort_descending(T * array,
size_t n)
108 size_t increment, i, j;
114 for (increment = 1; increment <= n / 9; increment = 3 * increment + 1) ;
116 for ( ; increment > 0; increment /= 3)
118 for (i = increment + 1; i <= n; i += increment)
123 while ((j > increment) && (array[j - increment] < t))
125 array[j] = array[j - increment];
137 void quick_sort(T * array,
size_t n)
139 static const size_t STACK_SIZE = CHAR_BIT *
sizeof(int);
140 static const size_t THRESHOLD = 7;
142 size_t left_index = 0;
143 size_t right_index = n - 1;
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;
151 while (right_index > left_index)
153 if ((right_index - left_index) > THRESHOLD)
156 middle = (left_index + right_index) / 2;
159 if (array[left_index] > array[middle])
161 temp = array[left_index];
162 array[left_index] = array[middle];
163 array[middle] = temp;
166 if (array[left_index] > array[right_index])
168 temp = array[left_index];
169 array[left_index] = array[right_index];
170 array[right_index] = temp;
173 if (array[middle] > array[right_index])
175 temp = array[middle];
176 array[middle] = array[right_index];
177 array[right_index] = temp;
180 pivot_index = right_index - 1;
182 temp = array[middle];
183 array[middle] = array[pivot_index];
184 array[pivot_index] = temp;
187 scan_left = left_index + 1;
188 scan_right = right_index - 2;
192 pivot_index = right_index;
193 scan_left = left_index;
194 scan_right = right_index - 1;
197 pivot = array[pivot_index];
202 while ((array[scan_left] < pivot) && (scan_left < right_index))
206 while ((array[scan_right] > pivot) && (scan_right > left_index))
210 if (scan_left >= scan_right)
214 temp = array[scan_right];
215 array[scan_right] = array[scan_left];
216 array[scan_left] = temp;
218 if (scan_left < right_index)
221 if (scan_right > left_index)
226 if (scan_left != pivot_index)
228 temp = array[pivot_index];
229 array[pivot_index] = array[scan_left];
230 array[scan_left] = temp;
234 size_left = scan_left - left_index;
235 size_right = right_index - scan_left;
237 if (size_left > size_right)
243 if (stack_ptr == STACK_SIZE)
244 throw std::runtime_error(
"stack overflow in quick_sort");
246 stack_left[stack_ptr] = left_index;
247 stack_right[stack_ptr] = scan_left - 1;
251 left_index = scan_left + 1;
261 if (stack_ptr == STACK_SIZE)
262 throw std::runtime_error(
"stack overflow in quick_sort");
264 stack_left[stack_ptr] = scan_left + 1;
265 stack_right[stack_ptr] = right_index;
269 right_index = scan_left - 1;
278 left_index = stack_left[stack_ptr];
279 right_index = stack_right[stack_ptr];