Auxiliary algorithms
[Algorithms]

---

Detailed Description

This group describes 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	counterSort (Iterator first, Iterator last, Functor functor)
	Sorts stable the stl compatible range into ascending order.

---

Function Documentation

void lemon::radixSort	(	Iterator	first,
		Iterator	last,
		Functor	functor
	)			[inline]

The radixSort sorts the stl compatible range into ascending order. The radix sort algorithm can sort the items which mapped to an integer by the adaptable unary function functor and the order will be ascending by these mapped values. As function specialization there is possible to use a normal function as the functor object or if the functor is not given it will use an identity function instead.

This implemented radix sort is a special quick sort which pivot value is choosen to partite the items on the next bit. This way, let be c the maximal capacity and n the number of the items in the container, the time complexity of the algorithm and the additional space complexity is .

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 wheter signed or unsigned.

void lemon::counterSort	(	Iterator	first,
		Iterator	last,
		Functor	functor
	)			[inline]

The counterSort sorts the stl compatible range into ascending order. The counter sort algorithm can sort the items which mapped to an integer by the adaptable unary function functor and the order will be ascending by these mapped values. As function specialization there is possible to use a normal function as the functor object or if the functor is not given it will use an identity function instead.

This implemented counter sort use a radix forward sort on the bytes of the integer. The algorithm can sort the items on a given byte. First time it counts how many times occurs a byte value in the container. By the occurence number it is possible to copy the container in the right order in O(n) time. The algorithm sorts the container by each bytes in forward direction which sorts the container by the whole value. This way, let be c the maximal capacity of the integer type and n the number of the items in the container, the time complexity of the algorithm and the additional space complexity is .

This sorting algorithm is stable so the order of two equal element stay in the same order.

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 wheter signed or unsigned.