22 #ifndef ELM_GENSTRUCT_QUICKSORT_H_
23 #define ELM_GENSTRUCT_QUICKSORT_H_
25 #include <elm/util/Comparator.h>
27 namespace elm {
namespace genstruct {
30 template <
class T,
template <
class>
class A,
class C>
32 static const int max = 300;
36 beg[0] = 0; end[0] = array.count();
38 L = beg[i]; R = end[i] - 1;
42 while(C::compare(array[R], piv) >= 0 && L < R) R--;
if(L < R) array[L++] = array[R];
43 while(C::compare(array[L], piv) <= 0 && L<R) L++;
if (L < R) array[R--] = array[L];
45 array[L] = piv; beg[i+1] = L+1; end[i+1] = end[i]; end[i++] = L;
46 if(end[i] - beg[i] > end[i-1] - beg[i-1]) {
47 swap = beg[i]; beg[i] = beg[i-1]; beg[i-1] =
swap;
48 swap = end[i]; end[i] = end[i-1]; end[i-1] =
swap;
const T & max(const T &x, const T &y)
Definition: compare.h:92
void swap(T &x, T &y)
Definition: misc.h:27
void quicksort(A< T > &array)
Definition: quicksort.h:31