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