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