All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Files | Functions
Auxiliary Algorithms
Algorithms

Detailed Description

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.
 

Function Documentation

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 2k 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.

Parameters
firstThe begin of the given range.
lastThe end of the given range.
functorAn adaptible unary function or a normal function which maps the items to any integer type which can be either signed or unsigned.
See Also
stableRadixSort()
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.

Parameters
firstThe begin of the given range.
lastThe end of the given range.
functorAn adaptible unary function or a normal function which maps the items to any integer type which can be either signed or unsigned.
See Also
radixSort()