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 #include <climits> 00042 00043 namespace libcoyotl 00044 { 00045 00046 //-------------------------------------------------- 00047 // sort two items 00048 00049 template<class T> 00050 inline void sort_two(T & a, T & b) 00051 { 00052 if (a > b) 00053 { 00054 T t = a; 00055 a = b; 00056 b = t; 00057 } 00058 } 00059 00060 //-------------------------------------------------- 00061 // sort three items 00062 00063 template<class T> 00064 inline void sort_three(T & a, T & b, T & c) 00065 { 00066 sort_two(a,b); 00067 sort_two(a,c); 00068 sort_two(b,c); 00069 } 00070 00071 //-------------------------------------------------- 00072 // shell sort an array in ascending order 00073 00074 template<class T> void 00075 shell_sort(T * a, size_t n) 00076 { 00077 size_t inc, i, j; 00078 T t; 00079 00080 // algorithm relies on one-based arrays 00081 --a; 00082 00083 for (inc = 1; inc <= n / 9; inc = 3 * inc + 1) ; 00084 00085 for ( ; inc > 0; inc /= 3) 00086 { 00087 for (i = inc + 1; i <= n; i += inc) 00088 { 00089 t = a[i]; 00090 j = i; 00091 00092 while ((j > inc) && (a[j - inc] > t)) 00093 { 00094 a[j] = a[j - inc]; 00095 j -= inc; 00096 } 00097 00098 a[j] = t; 00099 } 00100 } 00101 } 00102 00103 //-------------------------------------------------- 00104 // shell sort an array in ascending order 00105 00106 template<class T> 00107 void shell_sort_descending(T * array, size_t n) 00108 { 00109 size_t increment, i, j; 00110 T t; 00111 00112 // algorithm relies on one-based arrays 00113 --array; 00114 00115 for (increment = 1; increment <= n / 9; increment = 3 * increment + 1) ; 00116 00117 for ( ; increment > 0; increment /= 3) 00118 { 00119 for (i = increment + 1; i <= n; i += increment) 00120 { 00121 t = array[i]; 00122 j = i; 00123 00124 while ((j > increment) && (array[j - increment] < t)) 00125 { 00126 array[j] = array[j - increment]; 00127 j -= increment; 00128 } 00129 00130 array[j] = t; 00131 } 00132 } 00133 } 00134 00135 //-------------------------------------------------- 00136 // Quick Sort an array in ascending order 00137 template <class T> 00138 void quick_sort(T * array, size_t n) 00139 { 00140 static const size_t STACK_SIZE = CHAR_BIT * sizeof(int); 00141 static const size_t THRESHOLD = 7; 00142 00143 size_t left_index = 0; 00144 size_t right_index = n - 1; 00145 00146 T temp, pivot; 00147 size_t scan_left, scan_right, middle, pivot_index, size_left, size_right; 00148 size_t stack_left[STACK_SIZE], stack_right[STACK_SIZE], stack_ptr = 0; 00149 00150 while (true) 00151 { 00152 while (right_index > left_index) 00153 { 00154 if ((right_index - left_index) > THRESHOLD) 00155 { 00156 // "median-of-three" partitioning 00157 middle = (left_index + right_index) / 2; 00158 00159 // three-sort left, middle, and right elements 00160 if (array[left_index] > array[middle]) 00161 { 00162 temp = array[left_index]; 00163 array[left_index] = array[middle]; 00164 array[middle] = temp; 00165 } 00166 00167 if (array[left_index] > array[right_index]) 00168 { 00169 temp = array[left_index]; 00170 array[left_index] = array[right_index]; 00171 array[right_index] = temp; 00172 } 00173 00174 if (array[middle] > array[right_index]) 00175 { 00176 temp = array[middle]; 00177 array[middle] = array[right_index]; 00178 array[right_index] = temp; 00179 } 00180 00181 pivot_index = right_index - 1; 00182 00183 temp = array[middle]; 00184 array[middle] = array[pivot_index]; 00185 array[pivot_index] = temp; 00186 00187 // set-up for partitioning 00188 scan_left = left_index + 1; 00189 scan_right = right_index - 2; 00190 } 00191 else 00192 { 00193 pivot_index = right_index; 00194 scan_left = left_index; 00195 scan_right = right_index - 1; 00196 } 00197 00198 pivot = array[pivot_index]; 00199 00200 while (true) 00201 { 00202 // scan from left 00203 while ((array[scan_left] < pivot) && (scan_left < right_index)) 00204 ++scan_left; 00205 00206 // scan from right 00207 while ((array[scan_right] > pivot) && (scan_right > left_index)) 00208 --scan_right; 00209 00210 // if scans have met, exit inner loop 00211 if (scan_left >= scan_right) 00212 break; 00213 00214 // exchange elements 00215 temp = array[scan_right]; 00216 array[scan_right] = array[scan_left]; 00217 array[scan_left] = temp; 00218 00219 if (scan_left < right_index) 00220 ++scan_left; 00221 00222 if (scan_right > left_index) 00223 --scan_right; 00224 } 00225 00226 // exchange final element 00227 if (scan_left != pivot_index) 00228 { 00229 temp = array[pivot_index]; 00230 array[pivot_index] = array[scan_left]; 00231 array[scan_left] = temp; 00232 } 00233 00234 // place largest partition on stack 00235 size_left = scan_left - left_index; 00236 size_right = right_index - scan_left; 00237 00238 if (size_left > size_right) 00239 { 00240 if (size_left != 1) 00241 { 00242 ++stack_ptr; 00243 00244 if (stack_ptr == STACK_SIZE) 00245 throw std::runtime_error("stack overflow in quick_sort"); 00246 00247 stack_left[stack_ptr] = left_index; 00248 stack_right[stack_ptr] = scan_left - 1; 00249 } 00250 00251 if (size_right != 0) 00252 left_index = scan_left + 1; 00253 else 00254 break; 00255 } 00256 else 00257 { 00258 if (size_right != 1) 00259 { 00260 ++stack_ptr; 00261 00262 if (stack_ptr == STACK_SIZE) 00263 throw std::runtime_error("stack overflow in quick_sort"); 00264 00265 stack_left[stack_ptr] = scan_left + 1; 00266 stack_right[stack_ptr] = right_index; 00267 } 00268 00269 if (size_left != 0) 00270 right_index = scan_left - 1; 00271 else 00272 break; 00273 } 00274 } 00275 00276 // iterate with values from stack 00277 if (stack_ptr > 0) 00278 { 00279 left_index = stack_left[stack_ptr]; 00280 right_index = stack_right[stack_ptr]; 00281 00282 --stack_ptr; 00283 } 00284 else 00285 break; 00286 } 00287 } 00288 00289 } // end namespace libcoyotl 00290 00291 #endif 00292
© 1996-2005 Scott Robert Ladd. All rights reserved.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.