Files CCore/inc/Sort.h CCore/src/Sort.cpp
Subfolders CCore/inc/sort CCore/src/sort
For the theory and algorithm descriptions go to the Knuth. But programming is not a theory. Mostly it's about a theory implementation. And a good theory can be ruined by a stupid realization. That is why we use in CCore our own sort algorithms implementations.
Sorting is a permutating a given range of objects to arrange them in the ascending order relative the given linear order relation. Any permutation can be done by a series of transpositions of elements. So CCore implements sorting on the swap-based basis. I.e. a sorting process includes the performing two operations: comparison of elements and swapping them. That is a difference from other implementations, where objects are copied, not swapped. As was mentioned before, swap is efficient, but copying is expensive, not safe and not always possible. The second feature of our sorts is they takes a less comparison operations. This is important, because in real applications this operation can be quit expensive.
We use the term ran for a random access iterator. Usually it is just an ordinary pointer. Rans are used to access sort range elements.
There are following Algorithm Packages: ShortSort, HeapSort, QuickSort, MergeSort, and ParaQuickSort.
All sort algorithms are performed in a sort context. There are two common sort contexts: SortCtx for the range sorting and SortIndexCtx for the index sorting. An object of a sort context type is required to perform a sort.
template <class Ran>
struct SortCtx
{
static void swap(Ran a,Ran b) { Swap(*a,*b); }
static bool less(Ran a,Ran b) { return *a < *b ; }
};
SortCtx is a common sort context. It defines two methods: swap() to swap objects and less() to compare objects, pointed by two rans.
template <class T>
struct SortIndexCtx
{
T *base;
SortIndexCtx(T *base_) : base(base_) {}
template <class Ind>
static void swap(Ind *a,Ind *b) { Swap(*a,*b); }
template <class Ind>
bool less(const Ind *a,const Ind *b) const { return base[*a] < base[*b] ; }
};
SortIndexCtx is a sort context for index sorting. It contains a pointer to the object range. In index sort we don't modify the given object range, we create an array of indexes and sort it instead. To perform the comparison we need the base pointer of the range. The ran here is the Ind *.
Sort Algorithm Packages use the following pattern:
template <class Ran,class Ctx=SortCtx<Ran> >
struct XXXSort
{
template <class Len>
static void Sort(Ran ptr,Len len,Ctx ctx);
template <class Len>
static void Sort(Ran ptr,Len len) { Sort(ptr,len,Ctx()); }
};
Ran is a ran type and Ctx is a sort context type, defaulted to the SortCtx<Ran>. ptr is the pointer to the begin of the object range, len is the range length. ctx is the sort context.
ShortSort is the Algorithm Package to sort short ranges.
template <class Ran,class Ctx=SortCtx<Ran> >
struct ShortSort
{
// general
static void Sort2(Ran a,Ran b,Ctx ctx);
static void Sort3(Ran a,Ran b,Ran c,Ctx ctx);
static void Sort4(Ran a,Ran b,Ran c,Ran d,Ctx ctx);
static void Sort5(Ran a,Ran b,Ran c,Ran d,Ran e,Ctx ctx);
// array
static void Sort2(Ran a,Ctx ctx) { Sort2(a,a+1,ctx); }
static void Sort3(Ran a,Ctx ctx) { Sort3(a,a+1,a+2,ctx); }
static void Sort4(Ran a,Ctx ctx) { Sort4(a,a+1,a+2,a+3,ctx); }
static void Sort5(Ran a,Ctx ctx) { Sort5(a,a+1,a+2,a+3,a+4,ctx); }
// default
static void Sort2(Ran a) { Sort2(a,Ctx()); }
static void Sort3(Ran a) { Sort3(a,Ctx()); }
static void Sort4(Ran a) { Sort4(a,Ctx()); }
static void Sort5(Ran a) { Sort5(a,Ctx()); }
// combined
template <class Len>
static bool Sort(Ran a,Len len,Ctx ctx);
template <class Len>
static bool Sort(Ran a,Len len);
};
Currently ShortSort provides algorithms to sort 2, 3, 4 and 5 elements sets.
General SortX() sorts the given set of objects, pointed by rans in the given sort context.
(Default) array SortX() sorts the given range of the length X in the given (default) sort context.
Finally, the algorithm Sort() is a combination off all above. It sorts the given short array in the given or default sort context. Sort() returns false if the length is too large, and true if the length is allowed.
HeapSort implements the heap sort algorithm. This algorithm has a guaranteed O(N*log(N)) complexity, but it is not the fastest in a common case and it is CPU cache unfriendly. So the heap sort usually is used as the last resort to speed up the quick sort algorithm, which is faster in a common case, but has a bigger run time in special cases.
template <class Ran,class Ctx=SortCtx<Ran> >
struct HeapSort
{
template <class Len>
static void Sort(Ran ptr,Len len,Ctx ctx);
template <class Len>
static void Sort(Ran ptr,Len len) { Sort(ptr,len,Ctx()); }
};
QuickSort implements the quick sort algorithm. This is the main sort algorithm, because it has the best speed in a common case. It is also CPU cache friendly, that is important when sorting large arrays. To ensure O(N*log(N)) complexity, the implementation switches to the heap sort, if the quick sort goes badly.
template <class Ran,class Ctx=SortCtx<Ran> >
struct QuickSort
{
template <class Len>
static void Sort(Ran a,Len len,Ctx ctx);
template <class Len>
static void Sort(Ran a,Len len) { Sort(a,len,Ctx()); }
};
MergeSort implements the merge sort algorithm. It uses less comparison operations than the quick sort in common case, but more swap operations. So in general QuickSort is faster. However, in some cases when the comparison is an expensive, MergeSort is preferred.
MergeSort uses a temporary index buffer of the length of twice, than the original range length. It allocates this buffer in the stack, if it is short enough, or in the heap otherwise. If the allocation has failed, the quick sort is performed. You may use the methods MedSort to sort with a stack buffer. These methods perform sort and return true, if the length is acceptable. Otherwise, they return false.
template <class Ran,class Ctx=SortCtx<Ran> >
struct MergeSort
{
template <class Len>
static bool MedSort(Ran a,Len len,Ctx ctx);
template <class Len>
static bool MedSort(Ran a,Len len) { return MedSort(a,len,Ctx()); }
template <class Len>
static void Sort(Ran a,Len len,Ctx ctx);
template <class Len>
static void Sort(Ran a,Len len) { Sort(a,len,Ctx()); }
};
ParaQuickSort is a parallel version of the QuickSort. It requires multiple core CPU to be faster. ParaQuickSort uses a working thread pool. To get a speed benefit you have to start it.
Job::Init job_init; ParaQuickSort<....>::Sort(....);
template <class Ran,class Ctx=SortCtx<Ran> >
struct ParaQuickSort
{
template <class Len>
static void Sort(Ran a,Len len,Ctx ctx);
template <class Len>
static void Sort(Ran a,Len len) { Sort(a,len,Ctx()); }
};
Finally, here is the list of common sort functions:
template <class Ran,class Len> void Sort(Ran ptr,Len len); template <class T> void Sort(PtrLen<T> range); template <class Ran,class Len,class Func> void IncrSort(Ran ptr,Len len,Func less); template <class Ran,class Len,class Func> void DecrSort(Ran ptr,Len len,Func less); template <class T,class Func> void IncrSort(PtrLen<T> range,Func less); template <class T,class Func> void DecrSort(PtrLen<T> range,Func less);
IncrSort sorts in increasing order relative the functor less.
DecrSort sorts in decreasing order relative the functor less.
The following functions can be used to sort a reverse range.
template <class T,class Func> void IncrSort(PtrLenReverse<T> range,Func less); template <class T,class Func> void DecrSort(PtrLenReverse<T> range,Func less); template <class T> void Sort(PtrLenReverse<T> range);
The order of sorting is a native reverse range order. I.e. after the Sort() the following is true: range[0] < range[1] < range[2] < ....
There are two special sort contexts to sort with the given less functor:
/* struct IncrSortCtx<Ran,Func> */ template <class Ran,class Func> struct IncrSortCtx : SortCtx<Ran> { Func func; IncrSortCtx(const Func &func_) : func(func_) {} bool less(Ran a,Ran b) { return func(*a,*b); } }; /* struct DecrSortCtx<Ran,Func> */ template <class Ran,class Func> struct DecrSortCtx : SortCtx<Ran> { Func func; DecrSortCtx(const Func &func_) : func(func_) {} bool less(Ran a,Ran b) { return func(*b,*a); } };