Auxiliary 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 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.

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.

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

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.

See Also

radixSort()