Created by Scott Robert Ladd at Coyote Gulch Productions.
00001 //--------------------------------------------------------------------- 00002 // Algorithmic Conjurings @ http://www.coyotegulch.com 00003 // 00004 // sortutil.h 00005 // 00006 // Generic tools for sorting C-type arrays of data. 00007 //--------------------------------------------------------------------- 00008 // 00009 // Copyright 1990-2005 Scott Robert Ladd 00010 // 00011 // This program is free software; you can redistribute it and/or modify 00012 // it under the terms of the GNU General Public License as published by 00013 // the Free Software Foundation; either version 2 of the License, or 00014 // (at your option) any later version. 00015 // 00016 // This program is distributed in the hope that it will be useful, 00017 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00019 // GNU General Public License for more details. 00020 // 00021 // You should have received a copy of the GNU General Public License 00022 // along with this program; if not, write to the 00023 // Free Software Foundation, Inc. 00024 // 59 Temple Place - Suite 330 00025 // Boston, MA 02111-1307, USA. 00026 // 00027 //----------------------------------------------------------------------- 00028 // 00029 // For more information on this software package, please visit 00030 // Scott's web site, Coyote Gulch Productions, at: 00031 // 00032 // http://www.coyotegulch.com 00033 // 00034 //----------------------------------------------------------------------- 00035 00036 #if !defined(LIBCOYOTL_SORTUTIL_H) 00037 #define LIBCOYOTL_SORTUTIL_H 00038 00039 #include <stdexcept> 00040 00041 namespace libcoyotl 00042 { 00043 00044 //-------------------------------------------------- 00045 // sort two items 00046 00047 template<class T> 00048 inline void sort_two(T & a, T & b) 00049 { 00050 if (a > b) 00051 { 00052 T t = a; 00053 a = b; 00054 b = t; 00055 } 00056 } 00057 00058 //-------------------------------------------------- 00059 // sort three items 00060 00061 template<class T> 00062 inline void sort_three(T & a, T & b, T & c) 00063 { 00064 sort_two(a,b); 00065 sort_two(a,c); 00066 sort_two(b,c); 00067 } 00068 00069 //-------------------------------------------------- 00070 // shell sort an array in ascending order 00071 00072 template<class T> void 00073 shell_sort(T * a, size_t n) 00074 { 00075 size_t inc, i, j; 00076 T t; 00077 00078 // algorithm relies on one-based arrays 00079 --a; 00080 00081 for (inc = 1; inc <= n / 9; inc = 3 * inc + 1) ; 00082 00083 for ( ; inc > 0; inc /= 3) 00084 { 00085 for (i = inc + 1; i <= n; i += inc) 00086 { 00087 t = a[i]; 00088 j = i; 00089 00090 while ((j > inc) && (a[j - inc] > t)) 00091 { 00092 a[j] = a[j - inc]; 00093 j -= inc; 00094 } 00095 00096 a[j] = t; 00097 } 00098 } 00099 } 00100 00101 //-------------------------------------------------- 00102 // shell sort an array in ascending order 00103 00104 template<class T> 00105 void shell_sort_descending(T * array, size_t n) 00106 { 00107 size_t increment, i, j; 00108 T t; 00109 00110 // algorithm relies on one-based arrays 00111 --array; 00112 00113 for (increment = 1; increment <= n / 9; increment = 3 * increment + 1) ; 00114 00115 for ( ; increment > 0; increment /= 3) 00116 { 00117 for (i = increment + 1; i <= n; i += increment) 00118 { 00119 t = array[i]; 00120 j = i; 00121 00122 while ((j > increment) && (array[j - increment] < t)) 00123 { 00124 array[j] = array[j - increment]; 00125 j -= increment; 00126 } 00127 00128 array[j] = t; 00129 } 00130 } 00131 } 00132 00133 //-------------------------------------------------- 00134 // Quick Sort an array in ascending order 00135 template <class T> 00136 void quick_sort(T * array, size_t n) 00137 { 00138 static const size_t STACK_SIZE = CHAR_BIT * sizeof(int); 00139 static const size_t THRESHOLD = 7; 00140 00141 size_t left_index = 0; 00142 size_t right_index = n - 1; 00143 00144 T temp, pivot; 00145 size_t scan_left, scan_right, middle, pivot_index, size_left, size_right; 00146 size_t stack_left[STACK_SIZE], stack_right[STACK_SIZE], stack_ptr = 0; 00147 00148 while (true) 00149 { 00150 while (right_index > left_index) 00151 { 00152 if ((right_index - left_index) > THRESHOLD) 00153 { 00154 // "median-of-three" partitioning 00155 middle = (left_index + right_index) / 2; 00156 00157 // three-sort left, middle, and right elements 00158 if (array[left_index] > array[middle]) 00159 { 00160 temp = array[left_index]; 00161 array[left_index] = array[middle]; 00162 array[middle] = temp; 00163 } 00164 00165 if (array[left_index] > array[right_index]) 00166 { 00167 temp = array[left_index]; 00168 array[left_index] = array[right_index]; 00169 array[right_index] = temp; 00170 } 00171 00172 if (array[middle] > array[right_index]) 00173 { 00174 temp = array[middle]; 00175 array[middle] = array[right_index]; 00176 array[right_index] = temp; 00177 } 00178 00179 pivot_index = right_index - 1; 00180 00181 temp = array[middle]; 00182 array[middle] = array[pivot_index]; 00183 array[pivot_index] = temp; 00184 00185 // set-up for partitioning 00186 scan_left = left_index + 1; 00187 scan_right = right_index - 2; 00188 } 00189 else 00190 { 00191 pivot_index = right_index; 00192 scan_left = left_index; 00193 scan_right = right_index - 1; 00194 } 00195 00196 pivot = array[pivot_index]; 00197 00198 while (true) 00199 { 00200 // scan from left 00201 while ((array[scan_left] < pivot) && (scan_left < right_index)) 00202 ++scan_left; 00203 00204 // scan from right 00205 while ((array[scan_right] > pivot) && (scan_right > left_index)) 00206 --scan_right; 00207 00208 // if scans have met, exit inner loop 00209 if (scan_left >= scan_right) 00210 break; 00211 00212 // exchange elements 00213 temp = array[scan_right]; 00214 array[scan_right] = array[scan_left]; 00215 array[scan_left] = temp; 00216 00217 if (scan_left < right_index) 00218 ++scan_left; 00219 00220 if (scan_right > left_index) 00221 --scan_right; 00222 } 00223 00224 // exchange final element 00225 if (scan_left != pivot_index) 00226 { 00227 temp = array[pivot_index]; 00228 array[pivot_index] = array[scan_left]; 00229 array[scan_left] = temp; 00230 } 00231 00232 // place largest partition on stack 00233 size_left = scan_left - left_index; 00234 size_right = right_index - scan_left; 00235 00236 if (size_left > size_right) 00237 { 00238 if (size_left != 1) 00239 { 00240 ++stack_ptr; 00241 00242 if (stack_ptr == STACK_SIZE) 00243 throw std::runtime_error("stack overflow in quick_sort"); 00244 00245 stack_left[stack_ptr] = left_index; 00246 stack_right[stack_ptr] = scan_left - 1; 00247 } 00248 00249 if (size_right != 0) 00250 left_index = scan_left + 1; 00251 else 00252 break; 00253 } 00254 else 00255 { 00256 if (size_right != 1) 00257 { 00258 ++stack_ptr; 00259 00260 if (stack_ptr == STACK_SIZE) 00261 throw std::runtime_error("stack overflow in quick_sort"); 00262 00263 stack_left[stack_ptr] = scan_left + 1; 00264 stack_right[stack_ptr] = right_index; 00265 } 00266 00267 if (size_left != 0) 00268 right_index = scan_left - 1; 00269 else 00270 break; 00271 } 00272 } 00273 00274 // iterate with values from stack 00275 if (stack_ptr > 0) 00276 { 00277 left_index = stack_left[stack_ptr]; 00278 right_index = stack_right[stack_ptr]; 00279 00280 --stack_ptr; 00281 } 00282 else 00283 break; 00284 } 00285 } 00286 00287 } // end namespace libcoyotl 00288 00289 #endif 00290
© 1996-2005 Scott Robert Ladd. All rights reserved.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.