This group contains some algorithms implemented in LEMON in order to make it easier to implement complex algorithms.
Files | |
file | radix_sort.h |
Radix sort. | |
Functions | |
template<typename Iterator , typename Functor > | |
void | radixSort (Iterator first, Iterator last, Functor functor) |
Sorts the STL compatible range into ascending order. | |
template<typename Iterator , typename Functor > | |
void | stableRadixSort (Iterator first, Iterator last, Functor functor) |
Sorts the STL compatible range into ascending order in a stable way. | |
void lemon::radixSort | ( | Iterator | first, |
Iterator | last, | ||
Functor | functor | ||
) |
The radixSort
sorts an STL compatible range into ascending order. The radix sort algorithm can sort items which are mapped to integers with an adaptable unary function functor
and 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 2^{k} for each k
. Therefore, the time complexity of the algorithm is O(log(c)*n) and it uses O(log(c)) additional space, where c
is the maximal value and n
is the number of the items in the container.
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. |
void lemon::stableRadixSort | ( | Iterator | first, |
Iterator | last, | ||
Functor | functor | ||
) |
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 c
is the maximal value and n
is the number of the items in the container.
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. |