Auxiliary Algorithms
The same group on the Doxygen site.
- group Auxiliary Algorithms
Auxiliary algorithms implemented in LEMON.
This group contains some algorithms implemented in LEMON in order to make it easier to implement complex algorithms.
Functions and other members
-
template< typename Iterator , typename Functor >
void radixSort(
) Sorts the STL compatible range into ascending order.
The
radixSortsorts an STL compatible range into ascending order. The radix sort algorithm can sort items which are mapped to integers with an adaptable unary functionfunctorand the order will be ascending according to these mapped values.It is also possible to use a normal function instead of the functor object. If the functor is not given it will use the identity function instead.
This is a special quick sort algorithm where the pivot values to split the items are choosen to be 2k for each
k. Therefore, the time complexity of the algorithm is O( log(c) * n ) and it uses O(log(c)) additional space, wherecis the maximal value andnis the number of the items in the container.See also
- Parameters:
first – The begin of the given range.
last – The end of the given range.
functor – An adaptible unary function or a normal function which maps the items to any integer type which can be either signed or unsigned.
-
template< typename Iterator , typename Functor >
void stableRadixSort(
) Sorts the STL compatible range into ascending order in a stable way.
This function sorts an STL compatible range into ascending order according to an integer mapping in the same as radixSort() does.
This sorting algorithm is stable, i.e. the order of two equal elements remains the same after the sorting.
This sort algorithm use a radix forward sort on the bytes of the integer number. The algorithm sorts the items byte-by-byte. First, it counts how many times a byte value occurs in the container, then it copies the corresponding items to another container in asceding order in O(n) time.
The time complexity of the algorithm is O( log(c) * n ) and it uses O(n) additional space, where
cis the maximal value andnis the number of the items in the container.See also
- Parameters:
first – The begin of the given range.
last – The end of the given range.
functor – An adaptible unary function or a normal function which maps the items to any integer type which can be either signed or unsigned.