36 #if !defined(LIBCOYOTL_SORTUTIL_H)
37 #define LIBCOYOTL_SORTUTIL_H
50 inline void sort_two(T & a, T & b)
64 inline void sort_three(T & a, T & b, T & c)
74 template<
class T>
void
75 shell_sort(T * a,
size_t n)
83 for (inc = 1; inc <= n / 9; inc = 3 * inc + 1) ;
85 for ( ; inc > 0; inc /= 3)
87 for (i = inc + 1; i <= n; i += inc)
92 while ((j > inc) && (a[j - inc] > t))
107 void shell_sort_descending(T * array,
size_t n)
109 size_t increment, i, j;
115 for (increment = 1; increment <= n / 9; increment = 3 * increment + 1) ;
117 for ( ; increment > 0; increment /= 3)
119 for (i = increment + 1; i <= n; i += increment)
124 while ((j > increment) && (array[j - increment] < t))
126 array[j] = array[j - increment];
138 void quick_sort(T * array,
size_t n)
140 static const size_t STACK_SIZE = CHAR_BIT *
sizeof(int);
141 static const size_t THRESHOLD = 7;
143 size_t left_index = 0;
144 size_t right_index = n - 1;
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;
152 while (right_index > left_index)
154 if ((right_index - left_index) > THRESHOLD)
157 middle = (left_index + right_index) / 2;
160 if (array[left_index] > array[middle])
162 temp = array[left_index];
163 array[left_index] = array[middle];
164 array[middle] = temp;
167 if (array[left_index] > array[right_index])
169 temp = array[left_index];
170 array[left_index] = array[right_index];
171 array[right_index] = temp;
174 if (array[middle] > array[right_index])
176 temp = array[middle];
177 array[middle] = array[right_index];
178 array[right_index] = temp;
181 pivot_index = right_index - 1;
183 temp = array[middle];
184 array[middle] = array[pivot_index];
185 array[pivot_index] = temp;
188 scan_left = left_index + 1;
189 scan_right = right_index - 2;
193 pivot_index = right_index;
194 scan_left = left_index;
195 scan_right = right_index - 1;
198 pivot = array[pivot_index];
203 while ((array[scan_left] < pivot) && (scan_left < right_index))
207 while ((array[scan_right] > pivot) && (scan_right > left_index))
211 if (scan_left >= scan_right)
215 temp = array[scan_right];
216 array[scan_right] = array[scan_left];
217 array[scan_left] = temp;
219 if (scan_left < right_index)
222 if (scan_right > left_index)
227 if (scan_left != pivot_index)
229 temp = array[pivot_index];
230 array[pivot_index] = array[scan_left];
231 array[scan_left] = temp;
235 size_left = scan_left - left_index;
236 size_right = right_index - scan_left;
238 if (size_left > size_right)
244 if (stack_ptr == STACK_SIZE)
245 throw std::runtime_error(
"stack overflow in quick_sort");
247 stack_left[stack_ptr] = left_index;
248 stack_right[stack_ptr] = scan_left - 1;
252 left_index = scan_left + 1;
262 if (stack_ptr == STACK_SIZE)
263 throw std::runtime_error(
"stack overflow in quick_sort");
265 stack_left[stack_ptr] = scan_left + 1;
266 stack_right[stack_ptr] = right_index;
270 right_index = scan_left - 1;
279 left_index = stack_left[stack_ptr];
280 right_index = stack_right[stack_ptr];