Scippy

SoPlex

Sequential object-oriented simPlex

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