27 #define SHELLSORTMAX 25 30 template <
class T,
class COMPARATOR >
31 void SPxShellsort(T* keys,
int end, COMPARATOR& compare,
int start = 0)
33 static const int incs[3] = {1, 5, 19};
38 for( k = 2; k >= 0; --k )
41 int first = h + start;
44 for( i = first; i <= end; ++i )
50 while( j >= first && compare(tempkey, keys[j-h]) < 0 )
72 template <
class T,
class COMPARATOR >
73 void SPxQuicksort(T* keys,
int end, COMPARATOR& compare,
int start = 0,
bool type =
true)
78 if( end <= start + 1 )
104 while( lo < end && compare(keys[lo], pivotkey) < 0 )
106 while( hi > start && compare(keys[hi], pivotkey) >= 0 )
111 while( lo < end && compare(keys[lo], pivotkey) <= 0 )
113 while( hi > start && compare(keys[hi], pivotkey) > 0 )
127 assert((hi == lo-1) || (type && hi == start) || (!type && lo == end));
132 while( lo < end && compare(pivotkey, keys[lo]) >= 0 )
139 assert(compare(keys[mid], pivotkey) == 0);
142 keys[lo] = keys[mid];
150 while( hi > start && compare(pivotkey, keys[hi]) <= 0 )
157 assert(compare(keys[mid], pivotkey) == 0);
160 keys[hi] = keys[mid];
168 if( hi - start <= end - lo )
193 if( end - start >= 1 )
200 for(
int i = start; i < end; ++i )
201 assert(compare(keys[i], keys[i+1]) <= 0);
218 template <
class T,
class COMPARATOR >
233 if( end < start + 1 )
235 else if( end == start + 1 )
244 assert(start2 < end);
246 for(
int i = start; i < start2 - 1; ++i )
247 assert(compare(keys[i], keys[i+1]) <= 0);
252 if( start2 + size >= end - 1 )
268 mid = (start2 + end)/2;
269 pivotkey = keys[mid];
278 while( lo < end && compare(keys[lo], pivotkey) < 0 )
280 while( hi > start2 && compare(keys[hi], pivotkey) >= 0 )
285 while( lo < end && compare(keys[lo], pivotkey) <= 0 )
287 while( hi > start2 && compare(keys[hi], pivotkey) > 0 )
301 assert((hi == lo-1) || (type && hi == start2) || (!type && lo == end));
306 while( lo < end && compare(pivotkey, keys[lo]) >= 0 )
313 assert(compare(keys[mid], pivotkey) == 0);
316 keys[lo] = keys[mid];
324 while( hi > start2 && compare(pivotkey, keys[hi]) <= 0 )
331 assert(compare(keys[mid], pivotkey) == 0);
334 keys[hi] = keys[mid];
342 for(
int i = start2; i < lo; ++i )
343 assert(compare(keys[i], pivotkey) <= 0);
347 if( 2*size <= hi - start2 )
349 return SPxQuicksortPart(keys, compare, start, hi+1, size, start2, end2, !type);
352 else if( size <= lo - start2 )
361 return SPxQuicksortPart(keys, compare, start, end, size+start2-lo, lo, end2, !type);
void SPxQuicksort(T *keys, int end, COMPARATOR &compare, int start=0, bool type=true)
Generic QuickSort implementation.
void SPxShellsort(T *keys, int end, COMPARATOR &compare, int start=0)
Everything should be within this namespace.
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.