1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file sorter.h 26 * @brief Generic QuickSort implementation. 27 */ 28 #ifndef _SORTER_H_ 29 #define _SORTER_H_ 30 31 #include <assert.h> 32 33 namespace soplex 34 { 35 #define SOPLEX_SHELLSORTMAX 25 36 37 /** shell-sort an array of data elements; use it only for arrays smaller than 25 entries */ 38 template < class T, class COMPARATOR > 39 void SPxShellsort(T* keys, int end, COMPARATOR& compare, int start = 0) 40 { 41 static const int incs[3] = {1, 5, 19}; /* sequence of increments */ 42 int k; 43 44 assert(start <= end); 45 46 for(k = 2; k >= 0; --k) 47 { 48 int h = incs[k]; 49 int first = h + start; 50 int i; 51 52 for(i = first; i <= end; ++i) 53 { 54 int j; 55 T tempkey = keys[i]; 56 57 j = i; 58 59 while(j >= first && compare(tempkey, keys[j - h]) < 0) 60 { 61 keys[j] = keys[j - h]; 62 j -= h; 63 } 64 65 keys[j] = tempkey; 66 } 67 } 68 } 69 70 71 72 /// Generic QuickSort implementation. 73 /** This template function sorts an array \p t holding \p n elements of 74 type T using \p compare for comparisons. Class COMPARATOR must provide 75 an overloaded operator()(const T& t1,const T& t2) which returns 76 - < 0, if \p t1 is to appear before \p t2, 77 - = 0, if \p t1 and \p t2 can appear in any order, or 78 - > 0, if \p t1 is to appear after \p t2. 79 */ 80 81 template < class T, class COMPARATOR > 82 void SPxQuicksort(T* keys, int end, COMPARATOR& compare, int start = 0, bool type = true) 83 { 84 assert(start >= 0); 85 86 /* nothing to sort for less than two elements */ 87 if(end <= start + 1) 88 return; 89 90 /* reduce end position to last element index */ 91 --end; 92 93 /* use quick-sort for long lists */ 94 while(end - start >= SOPLEX_SHELLSORTMAX) 95 { 96 T pivotkey; 97 T tmp; 98 int lo; 99 int hi; 100 int mid; 101 102 /* select pivot element */ 103 mid = start + (end - start) / 2; // Instead of (start + end)/2 because the 104 // latter can overflow if start + end > 105 // INT_MAX 106 pivotkey = keys[mid]; 107 108 /* partition the array into elements < pivot [start,hi] and elements >= pivot [lo,end] */ 109 lo = start; 110 hi = end; 111 112 for(;;) 113 { 114 if(type) 115 { 116 while(lo < end && compare(keys[lo], pivotkey) < 0) 117 lo++; 118 119 while(hi > start && compare(keys[hi], pivotkey) >= 0) 120 hi--; 121 } 122 else 123 { 124 while(lo < end && compare(keys[lo], pivotkey) <= 0) 125 lo++; 126 127 while(hi > start && compare(keys[hi], pivotkey) > 0) 128 hi--; 129 } 130 131 if(lo >= hi) 132 break; 133 134 tmp = keys[lo]; 135 keys[lo] = keys[hi]; 136 keys[hi] = tmp; 137 138 lo++; 139 hi--; 140 } 141 142 assert((hi == lo - 1) || (type && hi == start) || (!type && lo == end)); 143 144 /* skip entries which are equal to the pivot element (three partitions, <, =, > than pivot)*/ 145 if(type) 146 { 147 while(lo < end && compare(pivotkey, keys[lo]) >= 0) 148 lo++; 149 150 /* make sure that we have at least one element in the smaller partition */ 151 if(lo == start) 152 { 153 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */ 154 assert(compare(keys[mid], pivotkey) == 0); /* the pivot element did not change its position */ 155 156 tmp = keys[lo]; 157 keys[lo] = keys[mid]; 158 keys[mid] = tmp; 159 160 lo++; 161 } 162 } 163 else 164 { 165 while(hi > start && compare(pivotkey, keys[hi]) <= 0) 166 hi--; 167 168 /* make sure that we have at least one element in the smaller partition */ 169 if(hi == end) 170 { 171 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */ 172 assert(compare(keys[mid], pivotkey) == 0); /* the pivot element did not change its position */ 173 174 tmp = keys[hi]; 175 keys[hi] = keys[mid]; 176 keys[mid] = tmp; 177 178 hi--; 179 } 180 } 181 182 /* sort the smaller partition by a recursive call, sort the larger part without recursion */ 183 if(hi - start <= end - lo) 184 { 185 /* sort [start,hi] with a recursive call */ 186 if(start < hi) 187 { 188 SPxQuicksort(keys, hi + 1, compare, start, !type); 189 } 190 191 /* now focus on the larger part [lo,end] */ 192 start = lo; 193 } 194 else 195 { 196 if(lo < end) 197 { 198 SPxQuicksort(keys, end + 1, compare, lo, !type); 199 } 200 201 /* now focus on the larger part [start,hi] */ 202 end = hi; 203 } 204 205 type = !type; 206 } 207 208 /* use shell sort on the remaining small list */ 209 if(end - start >= 1) 210 { 211 SPxShellsort(keys, end, compare, start); 212 } 213 214 215 #ifdef CHECK_SORTING 216 217 for(int i = start; i < end; ++i) 218 assert(compare(keys[i], keys[i + 1]) <= 0); 219 220 #endif 221 } 222 223 224 /**@brief Generic implementation of Partial QuickSort. 225 * 226 * This template function sorts an array \p t holding \p n elements of 227 * type T partially using \p compare for comparisons, i.e. ensures that 228 * the \p size smallest elements are sorted to the front. 229 * 230 * Class COMPARATOR must provide an overloaded 231 * operator()(const T& t1,const T& t2) which returns 232 * - < 0, if \p t1 is to appear before \p t2, 233 * - = 0, if \p t1 and \p t2 can appear in any order, or 234 * - > 0, if \p t1 is to appear after \p t2. 235 * 236 * @param keys array of elements to be sorted between index start and end 237 * @param compare comparator 238 * @param start index of first element in range to be sorted 239 * @param end index of last element in range to be sorted, plus 1 240 * @param size guaranteed number of sorted elements 241 * @param start2 auxiliary start index of sub range used for recursive call 242 * @param end2 auxiliary end index of sub range used for recursive call 243 * @param type type of sorting, to be more flexable on degenerated cases 244 */ 245 template < class T, class COMPARATOR > 246 int SPxQuicksortPart(T* keys, COMPARATOR& compare, int start, int end, int size, int start2 = 0, 247 int end2 = 0, bool type = true) 248 { 249 assert(start >= 0); 250 251 /* nothing to sort for less than two elements */ 252 if(end < start + 1) 253 return 0; 254 else if(end == start + 1) 255 return 1; 256 257 /* we assume that range {start, ..., start2-1} already contains the start2-start smallest elements in sorted order; 258 * start2 has to lie in {start, ..., end-1} */ 259 if(start2 < start) 260 start2 = start; 261 262 #ifdef CHECK_SORTING 263 assert(start2 < end); 264 265 for(int i = start; i < start2 - 1; ++i) 266 assert(compare(keys[i], keys[i + 1]) <= 0); 267 268 #endif 269 assert(end2 <= end); 270 271 /* if all remaining elements should be sorted, we simply call standard quicksort */ 272 if(start2 + size >= end - 1) 273 { 274 SPxQuicksort(keys, end, compare, start2, type); 275 return end - 1; 276 } 277 278 T pivotkey; 279 T tmp; 280 int lo; 281 int hi; 282 int mid; 283 284 /* reduce end position to last element index */ 285 --end; 286 287 /* select pivot element */ 288 mid = (start2 + end) / 2; 289 pivotkey = keys[mid]; 290 291 /* partition the array into elements < pivot [start,hi] and elements >= pivot [lo,end] */ 292 lo = start2; 293 hi = end; 294 295 for(;;) 296 { 297 if(type) 298 { 299 while(lo < end && compare(keys[lo], pivotkey) < 0) 300 lo++; 301 302 while(hi > start2 && compare(keys[hi], pivotkey) >= 0) 303 hi--; 304 } 305 else 306 { 307 while(lo < end && compare(keys[lo], pivotkey) <= 0) 308 lo++; 309 310 while(hi > start2 && compare(keys[hi], pivotkey) > 0) 311 hi--; 312 } 313 314 if(lo >= hi) 315 break; 316 317 tmp = keys[lo]; 318 keys[lo] = keys[hi]; 319 keys[hi] = tmp; 320 321 lo++; 322 hi--; 323 } 324 325 assert((hi == lo - 1) || (type && hi == start2) || (!type && lo == end)); 326 327 /* skip entries which are equal to the pivot element (three partitions, <, =, > than pivot)*/ 328 if(type) 329 { 330 while(lo < end && compare(pivotkey, keys[lo]) >= 0) 331 lo++; 332 333 /* make sure that we have at least one element in the smaller partition */ 334 if(lo == start2) 335 { 336 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */ 337 assert(compare(keys[mid], pivotkey) == 0); /* the pivot element did not change its position */ 338 339 tmp = keys[lo]; 340 keys[lo] = keys[mid]; 341 keys[mid] = tmp; 342 343 lo++; 344 } 345 } 346 else 347 { 348 while(hi > start2 && compare(pivotkey, keys[hi]) <= 0) 349 hi--; 350 351 /* make sure that we have at least one element in the smaller partition */ 352 if(hi == end) 353 { 354 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */ 355 assert(compare(keys[mid], pivotkey) == 0); /* the pivot element did not change its position */ 356 357 tmp = keys[hi]; 358 keys[hi] = keys[mid]; 359 keys[mid] = tmp; 360 361 hi--; 362 } 363 } 364 365 #ifdef CHECK_SORTING 366 367 for(int i = start2; i < lo; ++i) 368 assert(compare(keys[i], pivotkey) <= 0); 369 370 #endif 371 372 /* if we only need to sort less than half of the "<" part, use partial sort again */ 373 if(2 * size <= hi - start2) 374 { 375 return SPxQuicksortPart(keys, compare, start, hi + 1, size, start2, end2, !type); 376 } 377 /* otherwise, and if we do not need to sort the ">" part, use standard quicksort on the "<" part */ 378 else if(size <= lo - start2) 379 { 380 SPxQuicksort(keys, hi + 1, compare, start2, !type); 381 return lo - 1; 382 } 383 /* otherwise we have to sort the "<" part fully (use standard quicksort) and the ">" part partially */ 384 else 385 { 386 SPxQuicksort(keys, hi + 1, compare, start2, !type); 387 return SPxQuicksortPart(keys, compare, start, end + 1, size + start2 - lo, lo, end2, !type); 388 } 389 } 390 391 } // namespace soplex 392 #endif // _SORTER_H_ 393