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